suppressWarnings(library("knitr"))
suppressWarnings(library("gplots"))
suppressWarnings(library("igraph"))
opts_chunk$set(tidy.opts=list(width.cutoff=80),tidy=TRUE,dev="png",dpi=150)

define the functions that will be used for extracting useful data

load_obj <- function(file.path){
  temp.space <- new.env()
  obj<-load(file.path, temp.space)
  obj2<-get(obj, temp.space)
  rm(temp.space)
  return(obj2)
}
maxScl <- function(df, dir='row', max_value=NULL, log_space=TRUE){
  if(dir=='row'){
    dir=1
  }else if(dir=='col'){
    dir=2
  }else{
    print("dir must be 'row' or 'col'.")
    return
  }
  if(is.null(max_value)){
    max_value=median(apply(df,dir,max))
  }
  if(log_space){
    df=expm1(df)
    max_value=expm1(max_value)
  }
  df_scl=sweep(df,dir,apply(df,dir,max),"/")
  df_scl=df_scl*max_value
  if(log_space){
    df_scl=log1p(df_scl)
  }
  return(df_scl)
}
module.match <- function(NMF_list, ref_rep='rep0', min.cor=0.5){
  NMF_Ms=list()
  NMF_Gs=list()
  NMF_Gs[[ref_rep]]=maxScl(NMF_list[[ref_rep]][["G"]],dir = 'col',max_value=1,log_space = F)
  num_M=dim(NMF_Gs[[ref_rep]])[2]
  num_gen=dim(NMF_Gs[[ref_rep]])[1]
  for(rep in setdiff(names(NMF_list),ref_rep)){
      ##match modules across different replicates
      n_G=NMF_list[[rep]][['G']]
      n_G=maxScl(n_G,dir = 'col',max_value=1,log_space = F)
      NMF_Gs[[rep]]=n_G
      match_ind=c()
      for(i in 1:num_M){
        vec=NMF_Gs[[ref_rep]][,i]
        vec_ind=which(vec>0.1)
        G_ind=which(apply(n_G,1,max)>0.1)
        use_ind=union(vec_ind,G_ind)
        cors=cor(vec[use_ind],n_G[use_ind,])
        cor_ind=which.max(cors)
        if(max(cors) < min.cor){ ##SHOULD RECORD THE CORRELATION SCORES AND SEE IF THERE ARE AMBIGUOUS MATCHES
          match_ind=c(match_ind,NaN)
          #print(paste(stage,"rep0 module",i-1,"has no match in",rep))
          NMF_Gs[[rep]][,i]=NaN
        }else{
          NMF_Gs[[rep]][,i]=n_G[,cor_ind]
          match_ind=c(match_ind,cor_ind)
        }
      }
      if(num_M!=length(unique(match_ind))){
        print(paste(stage,rep," modules with duplicated matches:"))
        for (i in match_ind[which(duplicated(match_ind))]){
          if(!is.na(i)){
            print(paste(toString(which(match_ind==i)-1), "from rep0 matched to",i-1))
          }
        }
        print(paste("modules with no match",toString(setdiff(c(1:num_M),unique(match_ind))-1)))
      }
      #NMF_Gs[[paste0("DS",stage)]][[rep]]=maxScl(NMF_Gs[[paste0("DS",stage)]][[rep]],dir = 'col')
      #NMF_tops[[rep]]=NMF_list[[rep]][["top30genes"]]
    }
  num_reps=length(names(NMF_list))
  for(m in colnames(NMF_Gs[[ref_rep]])){
    NMF_Ms[[m]]=matrix(nrow=num_gen,ncol = num_reps)
    rownames(NMF_Ms[[m]])=rownames(NMF_Gs[[ref_rep]])
    colnames(NMF_Ms[[m]])=paste0("rep",c(0:(num_reps-1)))
    for(rep in names(NMF_list)){
      NMF_Ms[[m]][,rep]=NMF_Gs[[rep]][,m]
    }
    max_w=apply(NMF_Ms[[m]],1, function(x) max(x,na.rm = T))
    #min_w=apply(NMF_Ms[[paste0("DS",stage)]][[paste0("Module",m)]],1,min)
    NMF_Ms[[m]]=NMF_Ms[[m]][-which(max_w<0.1), ,drop=F]
    re_ind=order(NMF_Ms[[m]][,ref_rep],decreasing = T)
    NMF_Ms[[m]]=NMF_Ms[[m]][re_ind,]
    #print(paste("Module",m,"# kept genes:",dim(NMF_Ms[[paste0("DS",stage)]][[paste0("Module",m)]])[1]))
  }
  return(NMF_Ms)
}

Load the NMF results for each stage (these data files are not provided due to their large sizes)

A best K (number of modules or n_component argument used for running NMF) is picked for each stage based on the stability of the results from 10 NMF runs with random initial conditions.

ZFHIGH_k=c(10)
ZFOBLONG_k=c(11)
ZFDOME_k=c(17)
ZF30_k=c(15)
ZF50_k=c(20)
ZFS_k=c(25)
ZF60_k=c(25)
ZF75_k=c(24)
ZF90_k=c(45)
ZFB_k=c(40)
ZF3S_k=c(31)
ZF6S_k=c(42)
stages=c("ZFHIGH","ZFOBLONG","ZFDOME","ZF30","ZF50","ZFS","ZF60","ZF75","ZF90","ZFB","ZF3S","ZF6S")
zf_C<-list()
zf_G<-list()
zf_top <- list()
zf_genes=c()
NMF_list=list()
module_match=list()
for(stage in stages){
  stage_k=get(paste0(stage,"_k"))[1]
  NMF_obj=load_obj(paste0("./Results/DS_stages/DS_",stage,"/result_tbls.Robj"))
  NMF_list[[stage]]=NMF_obj[[paste0("K=",stage_k)]][["rep0"]]
  zf_C[[stage]]=data.frame(NMF_list[[stage]][["C"]], stringsAsFactors = F)
  zf_G[[stage]]=data.frame(NMF_list[[stage]][["G"]], stringsAsFactors = F)
  colnames(zf_G[[stage]])=rownames(zf_C[[stage]])
  zf_genes=c(zf_genes, rownames(zf_G[[stage]]))
  zf_top[[stage]]=data.frame(NMF_list[[stage]][["top30genes"]], stringsAsFactors = F)
  module_match[[stage]]=module.match(NMF_obj[[paste0("K=",stage_k)]], ref_rep='rep0',min.cor=0.5)
}
[1] "ZFHIGH rep9  modules with duplicated matches:"
[1] "0, 9 from rep0 matched to 0"
[1] "modules with no match 8"
[1] "ZFOBLONG rep1  modules with duplicated matches:"
[1] "4, 8 from rep0 matched to 8"
[1] "modules with no match 10"
[1] "ZFDOME rep1  modules with duplicated matches:"
[1] "2, 5 from rep0 matched to 2"
[1] "modules with no match 3, 14"
[1] "ZFDOME rep2  modules with duplicated matches:"
[1] "2, 5 from rep0 matched to 5"
[1] "11, 12 from rep0 matched to 13"
[1] "modules with no match 2, 14"
[1] "ZFDOME rep3  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 13"
[1] "modules with no match 2"
[1] "ZFDOME rep4  modules with duplicated matches:"
[1] "2, 5 from rep0 matched to 5"
[1] "modules with no match 2, 14"
[1] "ZFDOME rep5  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 5"
[1] "modules with no match 14"
[1] "ZFDOME rep7  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 5"
[1] "modules with no match 16"
[1] "ZFDOME rep8  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 15"
[1] "modules with no match 2"
[1] "ZF50 rep1  modules with duplicated matches:"
[1] "5, 12 from rep0 matched to 5"
[1] "modules with no match 16"
[1] "ZF50 rep5  modules with duplicated matches:"
[1] "5, 12 from rep0 matched to 5"
[1] "modules with no match 16"
[1] "ZF50 rep8  modules with duplicated matches:"
[1] "5, 12 from rep0 matched to 5"
[1] "modules with no match 16"
[1] "ZFS rep3  modules with duplicated matches:"
[1] "13, 16 from rep0 matched to 13"
[1] "modules with no match 22"
[1] "ZFS rep4  modules with duplicated matches:"
[1] "16, 24 from rep0 matched to 16"
[1] "modules with no match 23"
[1] "ZFS rep5  modules with duplicated matches:"
[1] "13, 17 from rep0 matched to 23"
[1] "0, 24 from rep0 matched to 0"
[1] "modules with no match 22, 24"
[1] "ZFS rep6  modules with duplicated matches:"
[1] "17, 21 from rep0 matched to 22"
[1] "22, 24 from rep0 matched to 21"
[1] "modules with no match 10, 20"
[1] "ZFS rep7  modules with duplicated matches:"
[1] "16, 24 from rep0 matched to 20"
[1] "modules with no match 21, 23"
[1] "ZFS rep8  modules with duplicated matches:"
[1] "16, 24 from rep0 matched to 21"
[1] "modules with no match 13"
[1] "ZFS rep9  modules with duplicated matches:"
[1] "15, 19 from rep0 matched to 23"
[1] "16, 22 from rep0 matched to 13"
[1] "modules with no match 10, 24"
[1] "ZF60 rep4  modules with duplicated matches:"
[1] "0, 13 from rep0 matched to 17"
[1] "modules with no match 0"
[1] "ZF60 rep7  modules with duplicated matches:"
[1] "13, 15 from rep0 matched to 13"
[1] "modules with no match 24"
[1] "ZF75 rep1  modules with duplicated matches:"
[1] "13, 14 from rep0 matched to 14"
[1] "modules with no match 13"
[1] "ZF75 rep2  modules with duplicated matches:"
[1] "1, 20 from rep0 matched to 1"
[1] "modules with no match 13"
[1] "ZF75 rep4  modules with duplicated matches:"
[1] "1, 20 from rep0 matched to 1"
[1] "5, 22 from rep0 matched to 5"
[1] "modules with no match 0, 13"
[1] "ZF75 rep5  modules with duplicated matches:"
[1] "13, 14 from rep0 matched to 14"
[1] "1, 20 from rep0 matched to 1"
[1] "modules with no match 0, 13"
[1] "ZF75 rep6  modules with duplicated matches:"
[1] "13, 14 from rep0 matched to 14"
[1] "modules with no match 13"
[1] "ZF75 rep7  modules with duplicated matches:"
[1] "13, 14 from rep0 matched to 14"
[1] "1, 20 from rep0 matched to 1"
[1] "modules with no match 0, 13"
[1] "ZF75 rep8  modules with duplicated matches:"
[1] "13, 14 from rep0 matched to 14"
[1] "5, 22 from rep0 matched to 5"
[1] "modules with no match 13, 21"
[1] "ZF75 rep9  modules with duplicated matches:"
[1] "13, 14 from rep0 matched to 14"
[1] "modules with no match 13"
[1] "ZF90 rep1  modules with duplicated matches:"
[1] "modules with no match 15, 28, 37, 38, 39"
[1] "ZF90 rep2  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 14"
[1] "modules with no match 11, 23, 24, 37, 39, 44"
[1] "ZF90 rep3  modules with duplicated matches:"
[1] "8, 26 from rep0 matched to 8"
[1] "modules with no match 25, 26, 32, 35, 39, 41, 44"
[1] "ZF90 rep4  modules with duplicated matches:"
[1] "0, 6 from rep0 matched to 0"
[1] "8, 26 from rep0 matched to 8"
[1] "modules with no match 23, 25, 32, 37"
[1] "ZF90 rep5  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 14"
[1] "8, 26 from rep0 matched to 8"
[1] "modules with no match 26, 36, 37, 44"
[1] "ZF90 rep6  modules with duplicated matches:"
[1] "modules with no match 25, 35, 39, 40, 43, 44"
[1] "ZF90 rep7  modules with duplicated matches:"
[1] "8, 26 from rep0 matched to 8"
[1] "modules with no match 30, 32, 36, 42, 43"
[1] "ZF90 rep8  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 14"
[1] "modules with no match 34, 36, 37, 38, 40"
[1] "ZF90 rep9  modules with duplicated matches:"
[1] "5, 14 from rep0 matched to 14"
[1] "9, 38 from rep0 matched to 33"
[1] "modules with no match 11, 23, 25, 35, 37, 38, 42"
[1] "ZFB rep1  modules with duplicated matches:"
[1] "26, 38 from rep0 matched to 26"
[1] "modules with no match 25, 29, 34, 37"
[1] "ZFB rep2  modules with duplicated matches:"
[1] "4, 23 from rep0 matched to 4"
[1] "modules with no match 25, 26, 31, 33, 38, 39"
[1] "ZFB rep3  modules with duplicated matches:"
[1] "modules with no match 28, 33, 39"
[1] "ZFB rep4  modules with duplicated matches:"
[1] "4, 23 from rep0 matched to 4"
[1] "12, 24 from rep0 matched to 12"
[1] "modules with no match 26, 32, 33, 34, 38, 39"
[1] "ZFB rep5  modules with duplicated matches:"
[1] "12, 24 from rep0 matched to 12"
[1] "modules with no match 20, 27, 29, 33, 37, 39"
[1] "ZFB rep6  modules with duplicated matches:"
[1] "modules with no match 22, 25, 31, 32, 34"
[1] "ZFB rep7  modules with duplicated matches:"
[1] "4, 23 from rep0 matched to 4"
[1] "modules with no match 25, 29, 35, 39"
[1] "ZFB rep8  modules with duplicated matches:"
[1] "modules with no match 25, 31, 34"
[1] "ZFB rep9  modules with duplicated matches:"
[1] "12, 24 from rep0 matched to 12"
[1] "modules with no match 22, 24, 31, 34, 38"
[1] "ZF3S rep1  modules with duplicated matches:"
[1] "5, 24 from rep0 matched to 5"
[1] "modules with no match 28"
[1] "ZF3S rep2  modules with duplicated matches:"
[1] "17, 27 from rep0 matched to 17"
[1] "modules with no match 29"
[1] "ZF3S rep3  modules with duplicated matches:"
[1] "5, 24 from rep0 matched to 5"
[1] "26, 30 from rep0 matched to 30"
[1] "modules with no match 7, 24"
[1] "ZF3S rep4  modules with duplicated matches:"
[1] "5, 24 from rep0 matched to 5"
[1] "17, 27 from rep0 matched to 17"
[1] "modules with no match 27, 29, 30"
[1] "ZF3S rep5  modules with duplicated matches:"
[1] "5, 24 from rep0 matched to 5"
[1] "modules with no match 25, 29"
[1] "ZF3S rep6  modules with duplicated matches:"
[1] "17, 27 from rep0 matched to 17"
[1] "modules with no match 29, 30"
[1] "ZF3S rep7  modules with duplicated matches:"
[1] "5, 24 from rep0 matched to 5"
[1] "17, 27 from rep0 matched to 17"
[1] "26, 30 from rep0 matched to 24"
[1] "modules with no match 7, 29, 30"
[1] "ZF3S rep9  modules with duplicated matches:"
[1] "5, 24 from rep0 matched to 5"
[1] "modules with no match 7, 30"
[1] "ZF6S rep1  modules with duplicated matches:"
[1] "0, 25 from rep0 matched to 0"
[1] "16, 27 from rep0 matched to 16"
[1] "28, 32 from rep0 matched to 29"
[1] "modules with no match 25, 31, 37, 38, 40, 41"
[1] "ZF6S rep2  modules with duplicated matches:"
[1] "15, 27 from rep0 matched to 27"
[1] "modules with no match 9, 25, 34, 35, 38, 39, 40"
[1] "ZF6S rep3  modules with duplicated matches:"
[1] "0, 25 from rep0 matched to 0"
[1] "16, 27 from rep0 matched to 16"
[1] "9, 34 from rep0 matched to 8"
[1] "modules with no match 25, 30, 33, 39, 41"
[1] "ZF6S rep4  modules with duplicated matches:"
[1] "modules with no match 24, 25, 33, 35, 39, 40"
[1] "ZF6S rep5  modules with duplicated matches:"
[1] "modules with no match 30, 34, 37, 39"
[1] "ZF6S rep6  modules with duplicated matches:"
[1] "7, 21 from rep0 matched to 21"
[1] "modules with no match 30, 34, 35, 36, 38"
[1] "ZF6S rep7  modules with duplicated matches:"
[1] "16, 27 from rep0 matched to 27"
[1] "modules with no match 25, 34, 36, 37, 38, 39"
[1] "ZF6S rep8  modules with duplicated matches:"
[1] "16, 27 from rep0 matched to 16"
[1] "13, 34 from rep0 matched to 13"
[1] "modules with no match 30, 37, 38, 41"
[1] "ZF6S rep9  modules with duplicated matches:"
[1] "16, 27 from rep0 matched to 16"
[1] "13, 34 from rep0 matched to 13"
[1] "modules with no match 33, 34, 35, 37, 40"

Find and remove modules that are primarily driven by batch and noise from each stage

Batch modules are found using the BatchGene function in Seurat package. Noise modules are defined as the ones that are primarily driven by a single gene (the top ranked gene has a weight more than 3 times the weight of the second ranked gene).

zf_use = filter.modules(zf_C,zf_G,module_match = module_match, batch.cutoff = 0.715, batch.field = 3) #0.735good
[1] "Stage: ZFHIGH"
[1] "number of batches: 2"
[1] 0.8451613 0.1548387
[1] "Batch modules:"
[1] "8" "5" "0" "1"
[1] "Stage: ZFOBLONG"
[1] "number of batches: 2"
[1] 0.361809 0.638191
[1] "Batch modules:"
[1] "2" "9"
[1] "Stage: ZFDOME"
[1] "number of batches: 1"
[1] 1
[1] "Batch modules:"
NULL
[1] "Stage: ZF30"
[1] "number of batches: 2"
[1] 0.2974768 0.7025232
[1] "Batch modules:"
[1] "3" "5"
[1] "Stage: ZF50"
[1] "number of batches: 4"
[1] 0.2195122 0.2439024 0.2672693 0.2693160
[1] "Batch modules:"
[1] "3"  "4"  "10" "16" "9"  "7"  "0" 
[1] "Stage: ZFS"
[1] "number of batches: 1"
[1] 1
[1] "Batch modules:"
NULL
[1] "Stage: ZF60"
[1] "number of batches: 3"
[1] 0.3470602 0.3034992 0.3494406
[1] "Batch modules:"
[1] "5"  "15" "13" "17"
[1] "Noise modules:"
[1] "23"
[1] "Stage: ZF75"
[1] "number of batches: 3"
[1] 0.3149905 0.4685326 0.2164769
[1] "Batch modules:"
[1] "4"  "23" "21" "16"
[1] "Noise modules:"
[1] "0"
[1] "Stage: ZF90"
[1] "number of batches: 3"
[1] 0.2200498 0.5063989 0.2735514
[1] "Batch modules:"
[1] "24" "9"  "23"
[1] "Noise modules:"
 [1] "6"  "29" "31" "33" "34" "35" "36" "37" "38" "39" "40" "41" "43" "44"
[1] "Stage: ZFB"
[1] "number of batches: 2"
[1] 0.03492596 0.07069014 0.66429170 0.23009220
[1] "Batch modules:"
[1] "15"
[1] "Noise modules:"
 [1] "20" "26" "27" "28" "30" "32" "34" "35" "36" "37" "38" "39"
[1] "Stage: ZF3S"
[1] "number of batches: 1"
[1] 1
[1] "Batch modules:"
NULL
[1] "Noise modules:"
[1] "28" "29"
[1] "Stage: ZF6S"
[1] "number of batches: 2"
[1] 0.5317763 0.4682237
[1] "Batch modules:"
[1] "25" "8" 
[1] "Noise modules:"
 [1] "24" "28" "30" "31" "32" "33" "36" "38" "39" "41"

Figure out how many top genes to use for calculating overlap scores

For each stage, calculate the coefficient of variance (CV) and a ‘specificity score’ for each gene’s weight in each module across the 10 replications. To calculate the CV of a gene in a particular module, we first extract that module from each of the 10 NMF runs (modules are matched by correlation of gene weigths). Then the CV of a gene in this module is defined as the mean of its weights divided by the standard deviation of its weights across these 10 replications. The specificity score of a gene for a module is calculated as the weight of the gene in that module divided by the sum of the gene’s weights in all modules from the same run. If a gene is a ‘robust’ marker of the module, it should have a small CV and a high specificity. We then plot these statistics of the top ranking genes in each module to see when CV becomes high and specificity becomes low, indicating the genes ranked higher than that are good genes to use in the overlap score calculations.

weight_cv=list()
for(stage in names(zf_use$match)){
  #num_gen=min(unlist(lapply(zf_use$match[[stage]], function(x) dim(x)[1])))
  num_gen=40
  weight_cv[[stage]]=matrix(nrow=num_gen, ncol = length(zf_use$match[[stage]]))
  colnames(weight_cv[[stage]])=names(zf_use$match[[stage]])
  for(m in names(zf_use$match[[stage]])){
    num_val = min(num_gen,dim(zf_use$match[[stage]][[m]])[1])
    weight_cv[[stage]][1:num_val,m]=apply(zf_use$match[[stage]][[m]][1:num_val,], 1, function(x) sqrt(var(x,na.rm = T))/mean(x, na.rm=T))
  }
}
weight_spec=list()
for(stage in names(zf_use$match)){
  weight_spec[[stage]]=zf_use$G[[stage]]
  rownames(weight_spec[[stage]])=1:dim(zf_use$G[[stage]])[1]
  weight_spec[[stage]]=sweep(weight_spec[[stage]],1,apply(zf_use$G[[stage]],1,sum),"/")
  for(i in 1:dim(zf_use$G[[stage]])[2]){
    ind_i=order(zf_use$G[[stage]][,i],decreasing = T)
    weight_spec[[stage]][,i]=weight_spec[[stage]][ind_i,i]
  }
}
par(mfrow=c(2,2))
for(stage in names(weight_cv)){
  plot(1:dim(weight_cv[[stage]])[1],apply(weight_cv[[stage]],1,function(x) mean(x,na.rm=T)),main=stage, ylab="Mean CV",xlab="Rank")
  plot(1:40,apply(weight_spec[[stage]][1:40,],1,function(x) mean(x,na.rm=T)),main=stage, ylab="Mean Specificity",xlab="Rank")
  plot(1:dim(weight_cv[[stage]])[1],apply(weight_cv[[stage]],1,function(x) median(x,na.rm=T)),main=stage, ylab="Median CV",xlab="Rank")
  plot(1:40,apply(weight_spec[[stage]][1:40,],1,function(x) median(x,na.rm=T)),main=stage, ylab="Median Specificity",xlab="Rank")
}

Calculate the weighted overlap between pairs of gene modules in adjacent stages

We decided to use the top 25 genes in each module in this calculation. The overlap of two modules is calculated as the sum of the weights of shared genes divided by the sum of weights of all genes. The results of the overlap scores are visualized in heat maps.

Calculate overlap between modules in every other stage

If a stage was not deeply or comprehensively sampled and sequenced, we might not be able to recover certain modules from that stage. This could potentially create dis-connections in the module lineages. In order to produce continuous module lineages when there is potential occasional drop-out of modules, we allow modules separated by one stage to connect to each other when connection to immediate neighbouring stage is not found.

Connect modules using the overlap scores calculated above

Build tables that record potential connections

For each module, find its most overlaped module in each of the two previous stages. Only modules with >22.5% overlaps are taken into account.

## for each module at one stage, want to find max correlated one in the two previous stages
connect_module <- function(thres1=0.15, thres2=0.25,G_cor_use,G_cor_use2){
  G_connect <- list()
  for(i in 1:(length(stages)-1)){
    stage=stages[i]
    stage_next=stages[i+1]
    G_cor_stage=G_cor_use[[stage]]
    Max_pre=apply(G_cor_stage,1,order)
    Max_pre_ind=Max_pre[dim(Max_pre)[1],]
    Max_pre_M=colnames(G_cor_stage)[Max_pre_ind]
    Max_value=apply(G_cor_stage,1,max)
    has_pre_ind=which(Max_value>thres1)
    has_pre_M=rownames(G_cor_stage)[has_pre_ind]
    if(i==1){
      G_connect[[stage_next]]=data.frame(matrix(NA, nrow = 1, ncol = dim(G_cor_stage)[1]),row.names=stage)
      colnames(G_connect[[stage_next]])=rownames(G_cor_stage)
      G_connect[[stage_next]][,has_pre_M]=Max_pre_M[has_pre_ind]
      G_connect[[stage_next]]=G_connect[[stage_next]][,has_pre_M]
    }else{
      stage_pre=stages[i-1]
      G_cor_stage2=G_cor_use2[[stage_pre]]
      all_M=union(rownames(G_cor_stage2),rownames(G_cor_stage))
      G_connect[[stage_next]]=data.frame(matrix(NA, nrow = 2, ncol = length(all_M)),row.names=c(stage,stage_pre))
      colnames(G_connect[[stage_next]])=all_M
      G_connect[[stage_next]][1,has_pre_M]=Max_pre_M[has_pre_ind]
      G_cor_stage=G_cor_use2[[stage_pre]]
      Max_pre=apply(G_cor_stage,1,order)
      Max_pre_ind=Max_pre[dim(Max_pre)[1],]
      Max_pre_M=colnames(G_cor_stage)[Max_pre_ind]
      Max_value=apply(G_cor_stage,1,max)
      has_pre_ind=which(Max_value>thres2)
      has_pre_M2=rownames(G_cor_stage)[has_pre_ind]
      G_connect[[stage_next]][2,has_pre_M2]=Max_pre_M[has_pre_ind]
      G_connect[[stage_next]]=G_connect[[stage_next]][,union(has_pre_M,has_pre_M2)]
    }
  }
  return(G_connect)
}
G_int_connect=connect_module(G_cor_use = G_int, G_cor_use2 = G_int2, thres1 = 0.2,thres2 = 0.2)

Build an adjacency matrix to record the final connections between modules

We start from modules in the oldest stage (6-somites). Each module is first connected to its most overlaped module in the immediate previous stage. If no potential connection is recorded (in G_int_connect) for the immediate previous stage, it will then be connected to the module recorded for the stage earlier (if there is one). When the overlap between a module and its most overlapped module in the immediate previous stage is less than 35%, and at the same time it has more than 50% overlap with its most overlapped module two stages earlier, we then directly connect this module to the more previous module, and cut its connection to the one in the immidiate previous stage (this case didn’t occur here).

build_netM <- function(G_connect,G_cor_use,G_cor_use2,thres=NULL,thres_pre=NULL){
  nodes_names=c()
  for(i in 1:(length(stages)-1)){
    stage=stages[i+1]
    G_ans=G_connect[[stage]]
    nodes_names=union(nodes_names,paste0(stage,'_',colnames(G_ans)))
    nodes_names=union(nodes_names,paste0(stages[i],"_",G_ans[stages[i],which(!is.na(G_ans[stages[i],]))]))
    if(i>1){
      nodes_names=union(nodes_names,paste0(stages[i-1],"_",G_ans[stages[i-1],which(!is.na(G_ans[stages[i-1],]))]))
    }
  }
  num_nodes=length(nodes_names)
  net_M=matrix(0,ncol = num_nodes,nrow = num_nodes)
  rownames(net_M)=nodes_names
  colnames(net_M)=nodes_names
  
  for(i in 1:(length(stages)-1)){
    stage_pre=stages[i]
    stage=stages[i+1]
    G_ans=G_connect[[stage]]
    for(j in colnames(G_ans)){
      to_name=paste0(stage,'_',j)
      if(!is.na(G_ans[stage_pre,j])){
        from_M=G_ans[stage_pre,j]
        from_name=paste0(stage_pre,'_',from_M)
        ##get the correlation score to put in the connection matirx
        net_M[from_name,to_name]=G_cor_use[[stage_pre]][j,from_M]
      }
      if(i!=1){
        stage_pre2=stages[i-1]
        if(!is.na(G_ans[stage_pre2,j])){
          from_M2=G_ans[stage_pre2,j]
          from_name2=paste0(stage_pre2,"_",from_M2)
          if(is.na(G_ans[stage_pre,j])){
            net_M[from_name2,to_name]=G_cor_use2[[stage_pre2]][j,from_M2]
          }else if(!is.null(thres)){
            G_cor=G_cor_use[[stage_pre]][j,from_M]
            G_cor_pre=G_cor_use2[[stage_pre2]][j,from_M2]
            if(G_cor<thres && G_cor_pre>thres_pre){
              print(paste0("add ",from_name2," to ",to_name))
              net_M[from_name2,to_name]=G_cor_use2[[stage_pre2]][j,from_M2]
              print(paste0("delete ", from_name," to ",to_name))
              net_M[from_name,to_name]=0
              }
            }
          }
        }
      }
    }
  return(net_M)
}

net_int=build_netM(G_int_connect, G_int, G_int2, thres = 0.35, thres_pre = 0.5)

Trim path with poor quality

zf_top$ZF60

zf_top$ZF75
zf_top$ZF90

Calculate the average overlap score along each chain of connected gene modules

path_score=calc_path_qual(net_int)
hist(path_score,breaks = 50, main="average weighted overlap")

Keep only the paths with >0.44 average weighted overlap.

Most of the path with <0.44 average overlap were short or consist of either ubiquitous or lowly expressed genes.

end_nodes_bad=names(path_score[path_score<0.44])
for(node in end_nodes_bad){
  #print(get_upstream(net_int,node))
  bad_path=get_upstream(net_int,node)
  bad_tbl=matrix(nrow=20,ncol=length(bad_path))
  colnames(bad_tbl)=bad_path
  for(bad_node in bad_path){
    stage=unlist(strsplit(bad_node,"_"))[1]
    m=unlist(strsplit(bad_node,"_"))[2]
    bad_tbl[,bad_node]=as.character(zf_top[[stage]][1:20,paste0("Module.",m)])
  }
  print(bad_tbl)
}
      ZFOBLONG_7      ZFHIGH_2   
 [1,] "MID1IP1A"      "MID1IP1A" 
 [2,] "ILDR1A"        "STARD14"  
 [3,] "TDGF1"         "KRT18"    
 [4,] "PPDPFA"        "KLF17"    
 [5,] "CRELD2"        "GADD45BB" 
 [6,] "FTR83"         "CCND1"    
 [7,] "CDKN1CA"       "CDKN1CA"  
 [8,] "EF1"           "BTG1"     
 [9,] "GPR160"        "GADD45BA" 
[10,] "ZNHIT6"        "MPLKIP"   
[11,] "KLF17"         "LRWD1"    
[12,] "CLDNE"         "NET1"     
[13,] "FOXI1"         "CLDNE"    
[14,] "SI:CH73-1A9.3" "ARL13A"   
[15,] "GPAT2"         "GRHL3"    
[16,] "ACTB1"         "MARCKSL1B"
[17,] "ATP1B3A"       "ACKR3B"   
[18,] "ELOVL1B"       "SOX19A"   
[19,] "GNMT"          "IRX7"     
[20,] "SMPD5"         "RASSF7B"  
      ZFDOME_11        ZFOBLONG_3         
 [1,] "CST3"           "ALDOB"            
 [2,] "CD9B"           "ASB11"            
 [3,] "ATP1B1A"        "ID1"              
 [4,] "LRWD1"          "APOEB"            
 [5,] "FAM212AA"       "HSPB1"            
 [6,] "FAM46BA"        "SI:CH1073-80I24.3"
 [7,] "CABZ01070258.1" "TBX16"            
 [8,] "APELA"          "MALAT1"           
 [9,] "CXCR4A"         "ZGC:110425"       
[10,] "CX43.4"         "FAM212AA"         
[11,] "ABRACL"         "AKAP12B"          
[12,] "SSR3"           "SI:CH211-152C2.3" 
[13,] "TDGF1"          "NNR"              
[14,] "CXCR4B"         "CXCR4B"           
[15,] "CYP26A1"        "SI:CH73-1A9.3"    
[16,] "LRATB"          "CITED4B"          
[17,] "H2AFX"          "SI:DKEY-228B2.6"  
[18,] "ETV4"           "POLR3GLA"         
[19,] "ID1"            "CXCR4A"           
[20,] "ZIC2B"          "CABZ01070258.1"   
      ZFS_10             ZF50_18            ZF30_12             ZFDOME_8            ZFHIGH_3           
 [1,] "EPCAM"            "BLF"              "SI:CH1073-190K2.1" "H2AFX"             "PLK1"             
 [2,] "NNR"              "SI:CH211-133N4.4" "ACP5A"             "CTH1"              "CCNG1"            
 [3,] "CST3"             "SI:CH73-52F24.4"  "THY1"              "THY1"              "CTSBA"            
 [4,] "NPC2"             "CA9"              "CCNA1"             "CCNA1"             "F11R.1"           
 [5,] "H1M"              "OCLNA"            "NPC2"              "CTSBA"             "NUSAP1"           
 [6,] "CAPNS1A"          "MCM6"             "OCLNA"             "SNAI1A"            "TMEM263"          
 [7,] "CXCR4B"           "F11R.1"           "ZGC:113886"        "CCNG1"             "ANKRD12"          
 [8,] "DNAJB1B"          "EPCAM"            "MIBP"              "MPLKIP"            "CCNA1"            
 [9,] "OCLNA"            "TIFA"             "SPINT2"            "BLF"               "RNF128A"          
[10,] "PDIA6"            "SI:CH211-86H15.1" "FOPNL"             "SI:CH211-173M16.2" "CTH1"             
[11,] "SI:CH73-299H12.3" "ZGC:92818"        "TUBB4B"            "ZP3.2"             "CALR3B"           
[12,] "LRWD1"            "GDF3"             "GLULB"             "BTG2"              "RBM38"            
[13,] "SI:DKEY-68O6.5"   "NPC2"             "SI:CH211-173M16.2" "SEC61G"            "SI:CH211-269I23.2"
[14,] "F11R.1"           "CCNA1"            "SLC16A3"           "HSPA5"             "NPC2"             
[15,] "ATP1B1A"          "HMGB1A"           "CTSS2.1"           "SI:CH73-52F24.4"   "CDC14B"           
[16,] "EFHD1"            "CD9B"             "BLF"               "NPC2"              "SI:CH211-199G17.2"
[17,] "RRM2"             "SALL4"            "F11R.1"            "ZGC:158852"        "COQ10B"           
[18,] "FBXO5"            "SI:CH211-137A8.4" "SHISA2"            "DDIT4"             "BTG2"             
[19,] "HIST2H2AB"        "QKIA"             "CTH1"              "NDUFA4L"           "PRRG2"            
[20,] "CDCA7A"           "ZFAND5A"          "NNR"               "SEPH"              "GSTP1"            
      ZFS_0               ZF30_14             ZFDOME_14           ZFOBLONG_3         
 [1,] "SI:CH1073-80I24.3" "SI:CH73-281N10.2"  "KPNA2"             "ALDOB"            
 [2,] "HMGB1A"            "ID1"               "FBXO5"             "ASB11"            
 [3,] "NDUFA4L"           "HSPB1"             "INCENP"            "ID1"              
 [4,] "DYNLL2A"           "SEC61G"            "MAD2L1"            "APOEB"            
 [5,] "SEPH"              "CXCR4B"            "SOX3"              "HSPB1"            
 [6,] "HIST2H2AB"         "SOX3"              "PFKFB4B"           "SI:CH1073-80I24.3"
 [7,] "RPS20"             "VED"               "APOEB"             "TBX16"            
 [8,] "CFL1"              "RPS12"             "VED"               "MALAT1"           
 [9,] "STMN1A"            "ALDOB"             "POLR3GLA"          "ZGC:110425"       
[10,] "ZGC:92818"         "NNR"               "VOX"               "FAM212AA"         
[11,] "RPS18"             "ANP32E"            "ASB11"             "AKAP12B"          
[12,] "RPS12"             "ASB11"             "SEPT12"            "SI:CH211-152C2.3" 
[13,] "CDCA7A"            "MARCKSL1B"         "HSPB1"             "NNR"              
[14,] "SI:CH211-152C2.3"  "SI:DKEY-151G10.6"  "SI:CH211-133N4.4"  "CXCR4B"           
[15,] "SI:CH211-222L21.1" "SI:CH73-1A9.3"     "SI:CH211-152C2.3"  "SI:CH73-1A9.3"    
[16,] "SI:CH73-281N10.2"  "DYNLL1"            "SOX19A"            "CITED4B"          
[17,] "LRWD1"             "SI:CH211-152C2.3"  "SI:CH211-222L21.1" "SI:DKEY-228B2.6"  
[18,] "HSPB1"             "VOX"               "STM"               "POLR3GLA"         
[19,] "SI:DKEY-151G10.6"  "SI:CH211-222L21.1" "MALAT1"            "CXCR4A"           
[20,] "TUBA8L4"           "APOEB"             "TUBB4B"            "CABZ01070258.1"   
      ZFS_16            ZF30_7   
 [1,] "SRSF10B"         "TOP2A"  
 [2,] "CTSBA"           "KPNA2"  
 [3,] "SSR4"            "BIRC5A" 
 [4,] "BIRC5A"          "UBTF"   
 [5,] "FOXD5"           "CENPF"  
 [6,] "HMGB1A"          "ASPM"   
 [7,] "ALCAMB"          "LRWD1"  
 [8,] "SDC4"            "UBE2C"  
 [9,] "SSR3"            "PHO"    
[10,] "SLC37A2"         "ANKRD11"
[11,] "GAPDH"           "TPX2"   
[12,] "SI:DKEY-27I16.2" "PLK1"   
[13,] "YWHAQA"          "INCENP" 
[14,] "EIF3S10"         "FBXO5"  
[15,] "SNRNP40"         "ZC3H15" 
[16,] "DNAJB1B"         "ZNFL2A" 
[17,] "SEPT12"          "ZEB1A"  
[18,] "DNTTIP2"         "DNTTIP2"
[19,] "ZC3H15"          "BCL2L12"
[20,] "NUSAP1"          "SEPT12" 
      ZF75_12             ZF60_12             ZFS_8               ZF50_15   ZF30_8              ZFDOME_5            ZFOBLONG_4       
 [1,] "SI:CH1073-80I24.3" "SI:CH1073-80I24.3" "VED"               "VED"     "APOC1"             "VED"               "CST3"           
 [2,] "POLR3GLA"          "NNR"               "ID1"               "APOC1"   "VED"               "BAMBIA"            "NOTO"           
 [3,] "NNR"               "CXCR4B"            "APOEB"             "BAMBIA"  "APOEB"             "NOTO"              "TBX16"          
 [4,] "LRWD1"             "SI:DKEY-228B2.6"   "BAMBIA"            "APOEB"   "BAMBIA"            "ARL5C"             "SI:DKEY-228B2.6"
 [5,] "ADD3B"             "SOX3"              "APOC1"             "ID1"     "CALM3A"            "VOX"               "CMTM6"          
 [6,] "EIF4EBP3L"         "SI:CH211-173M16.2" "CITED4B"           "VOX"     "TUBB4B"            "BMP2B"             "BAIAP2L1A"      
 [7,] "DYNLL1"            "ASB11"             "SOX19A"            "BMP7A"   "SI:CH1073-80I24.3" "SI:DKEY-261J4.3"   "VOX"            
 [8,] "ASB11"             "LRWD1"             "SOX3"              "RGCC"    "RGCC"              "APOC1"             "FAM3C"          
 [9,] "ALDOB"             "GLULB"             "VOX"               "SOX3"    "H2AFX"             "APOEB"             "ANKRD11"        
[10,] "FKBP7"             "SI:DKEY-27I16.2"   "SI:CH1073-80I24.3" "CXCR4B"  "CTSBA"             "UBTF"              "AKAP12B"        
[11,] "MARCKSL1B"         "FBXO5"             "CXCR4B"            "SOX19A"  "MID1IP1B"          "BIRC5A"            "SOX11A"         
[12,] "GLULB"             "ZIC2B"             "FOXI1"             "GATA2A"  "NUSAP1"            "SI:DKEY-261J4.5"   "HSD17B12A"      
[13,] "SOX19A"            "SI:DKEY-68O6.5"    "RGCC"              "CITED4B" "VOX"               "CHD4B"             "FSCN1A"         
[14,] "MPLKIP"            "SOX19A"            "ID3"               "BMP4"    "GAPDH"             "SI:CH1073-80I24.3" "LFT2"           
[15,] "ZIC2B"             "POLR3GLA"          "POLR3GLA"          "ID2A"    "TP53INP2"          "RPL38"             "CALR"           
[16,] "CABZ01070258.1"    "ID1"               "MID1IP1B"          "RASL11B" "GLULB"             "TBX16"             "TP53INP2"       
[17,] "SOX11A"            "MPLKIP"            "ZIC2B"             "CRABP2B" "BCAS2"             "TIFA"              "STM"            
[18,] "CDCA7A"            "H2AFX"             "FAM212AB"          "CXCL12A" "SI:CH211-173M16.2" "CMTM6"             "PDAP1B"         
[19,] "CITED4B"           "SOX2"              "ALDOB"             "CXCR4A"  "ID3"               "STM"               "ZGC:110425"     
[20,] "CFL1L"             "DNAJB1B"           "ASB11"             "NNR"     "HER7"              "RPS20"             "EFHD1"          
      ZFHIGH_6           
 [1,] "NOTO"             
 [2,] "WNT11"            
 [3,] "GSC"              
 [4,] "FOXD3"            
 [5,] "SDF4"             
 [6,] "EZRB"             
 [7,] "STARD14"          
 [8,] "FOXA"             
 [9,] "TBX16"            
[10,] "SOX11A"           
[11,] "RASGEF1BA"        
[12,] "PARD6GB"          
[13,] "CEBPB"            
[14,] "NOG1"             
[15,] "PLK3"             
[16,] "SI:DKEY-108K21.14"
[17,] "BTG1"             
[18,] "ZGC:92066"        
[19,] "TOLLIP"           
[20,] "TSPAN15"          
      ZF3S_25            ZF90_19           ZF60_22           ZFS_13       ZF30_7   
 [1,] "ZC3H13"           "HELLS"           "PTMAA"           "ANKRD11"    "TOP2A"  
 [2,] "GUSB"             "CDCA7A"          "HELLS"           "ZC3H13"     "KPNA2"  
 [3,] "SSR3"             "MCM6"            "GOLGB1"          "SALL4"      "BIRC5A" 
 [4,] "PNN"              "CASP8AP2"        "CASP8AP2"        "ASPH"       "UBTF"   
 [5,] "DENR"             "NASP"            "CEP250"          "INCENP"     "CENPF"  
 [6,] "MYL12.1"          "NAP1L1"          "ANKRD11"         "BAZ1B"      "ASPM"   
 [7,] "EIF3S10"          "SEPH"            "MCM6"            "PLK1"       "LRWD1"  
 [8,] "ANP32E"           "UBTF"            "BAZ1B"           "CHD4B"      "UBE2C"  
 [9,] "UBTF"             "LIG1"            "SI:DKEY-56M19.5" "MKI67"      "PHO"    
[10,] "PTMAA"            "ZC3H13"          "PPRC1"           "CENPF"      "ANKRD11"
[11,] "NOP56"            "HMGB1A"          "ZC3H13"          "PNN"        "TPX2"   
[12,] "OST4"             "BAZ1B"           "CHD4B"           "PHO"        "PLK1"   
[13,] "SI:DKEY-238C7.12" "PPRC1"           "NAT8L"           "ZGC:110425" "INCENP" 
[14,] "KDELR2B"          "PCNA"            "MKI67"           "PPIG"       "FBXO5"  
[15,] "SALL4"            "PTMAA"           "ATP1B1A"         "HELLS"      "ZC3H15" 
[16,] "GLULB"            "PNN"             "DNTTIP2"         "NUSAP1"     "ZNFL2A" 
[17,] "CHD4B"            "HIRIP3"          "TUBA1A"          "RRP1"       "ZEB1A"  
[18,] "PHO"              "MARCKSL1A"       "ZC3H15"          "ACIN1A"     "DNTTIP2"
[19,] "LRRC59"           "SI:DKEY-56M19.5" "LRWD1"           "PPRC1"      "BCL2L12"
[20,] "ACIN1A"           "NOP56"           "MALAT1"          "CASP8AP2"   "SEPT12" 
end_nodes_good=names(path_score[path_score>=0.44])
all_nodes_good=c()
for(node in end_nodes_good){
  all_nodes_good=c(all_nodes_good,get_upstream(net_int,node))
}
all_nodes_good=unique(all_nodes_good)
net_int_good=net_int[all_nodes_good,all_nodes_good]
draw.net(net_int_good, circular = F,label.size = 0.37)

Save connected module information for overlaying on URD tree

For each module at the end (oldest developmental stage) of a connected chain, find all its upstream modules, and store them as an entry in one list

all_end_nodes=rownames(net_int_good)[which(apply(net_int_good,1,sum)==0)]
all_lineages<-list()
for(end_node in all_end_nodes){
  up_nodes=get_upstream(net_int_good,end_node)
  path_tbl=data.frame(matrix(nrow=25,ncol=2*length(up_nodes)),stringsAsFactors = F)
  name_col=rep(up_nodes,each=2)
  name_col[c(1:length(up_nodes))*2]=paste0(name_col[c(1:length(up_nodes))*2],"_Weight")
  colnames(path_tbl)=name_col
  for(node in up_nodes){
    stage=unlist(strsplit(node,"_"))[1]
    m=unlist(strsplit(node,"_"))[2]
    path_tbl[,node]=as.character(zf_top[[stage]][1:25,paste0("Module.",m)])
    path_tbl[,paste0(node,"_Weight")]=(zf_top[[stage]][1:25,paste0("Weights.",m)])
  }
  all_lineages[[end_node]]=path_tbl
}
#save(all_lineages,file="./Module_tree/module_lineages.Robj")

For modules that are in the same connected chain, sum up their levels in each cell to represent the expression of that lineage program. This results is a lineage by cell matrix

lineage_exp <- function(DS_C_use, DS_G_use, net_int_good, all_lineages, all_end_nodes=NULL){
  if(is.null(all_end_nodes)){
    all_end_nodes=rownames(net_int_good)[which(apply(net_int_good,1,sum)==0)]
  }
  stages=names(DS_C_use)
  all_cells=c()
  all_genes=c()
  for(stage in stages){
    C_use=DS_C_use[[stage]]
    all_cells=c(all_cells,colnames(C_use))
    G_use=DS_G_use[[stage]]
    all_genes=c(all_genes,rownames(G_use))
  }
  
  all_genes=unique(all_genes)
  all_Ms=rownames(net_int_good)
  allM_allCell=data.frame(matrix(0,ncol = length(all_cells),nrow = length(all_Ms)),row.names = all_Ms)
  allGene_allM=data.frame(matrix(0,ncol = length(all_Ms),nrow = length(all_genes)),row.names = all_genes)
  colnames(allM_allCell)=all_cells
  colnames(allGene_allM)=all_Ms
  ## look stage by stage, fill in the expression matrix with MAX NORMALIZED gene module expression 
  for(stage in stages){
    G_use=DS_G_use[[stage]]
    G.max=apply(G_use, 2, max)
    G_norm=sweep(G_use, 2, G.max, '/') ## now each module's top gene has weight 1
    colnames(G_norm)=paste0(stage,"_",colnames(G_norm))
    M_use=intersect(colnames(G_norm),all_Ms)
    
    C_use=DS_C_use[[stage]]
    C.max=apply(C_use, 1, max)
    C_norm=sweep(C_use,1,C.max,'/')
    rownames(C_norm)=paste0(stage,"_",rownames(C_norm))
    
    if(length(M_use)>0){
      ## fill in gene matrix
      allGene_allM[rownames(G_norm),M_use]=G_norm[rownames(G_norm),M_use]
      ## fill in cell matrix
      allM_allCell[M_use,colnames(C_use)]=C_norm[M_use,colnames(C_use)]
    }
  }
  
  lineage_cell=data.frame(matrix(0,ncol = length(all_cells),nrow = length(all_end_nodes)),row.names = all_end_nodes, stringsAsFactors = F)
  colnames(lineage_cell)=all_cells
  
  # matrix to use: allM_allCell
  for(lin in all_end_nodes){
    lin_M=colnames(all_lineages[[lin]])[c(T,F)]
    if(length(setdiff(lin_M,all_Ms))==0){
      ## sum up and add
      lineage_cell[lin,]=apply(allM_allCell[lin_M,colnames(lineage_cell)],2,sum)
    }else{
      print(paste(lin,"has module(s) that are not in the table"))
    }
  }
  return(list(lineageXcell=lineage_cell, allMXallCell=allM_allCell, allGeneXallM=allGene_allM))
}
lineage_module_list=lineage_exp(zf_use$C, zf_use$G, net_int_good, all_lineages, all_end_nodes=all_end_nodes)
lineage_cell=lineage_module_list$lineageXcell
allM_allCell=lineage_module_list$allMXallCell
allGene_allM=lineage_module_list$allGeneXallM

Define functions for visualizing the tree

clan_coord <- function(net_int_good, node_start, y.names=stages){
  y=rev(1:length(y.names))
  names(y)=y.names
  nodes_in_clan <- get_downstream(net_int_good,node_start)
  clan_net <- net_int_good[nodes_in_clan,nodes_in_clan]
  end_nodes <- rownames(clan_net)[which(apply(clan_net,1,sum)==0)]
  coords=matrix(nrow=length(nodes_in_clan),ncol = 2)
  rownames(coords)=nodes_in_clan
  colnames(coords)=c("x","y")
  m.stages=unlist(lapply(nodes_in_clan, function(x) unlist(strsplit(x,"_"))[1]))
  ys=y[m.stages]
  coords[,"y"]=ys
  if(length(end_nodes)==1){
    xs=rep(0, length(nodes_in_clan))
    names(xs)=nodes_in_clan
    coords[,"x"]=xs[rownames(coords)]
    return(coords)
  }else{
    up_nodes <- list()
    for(node in end_nodes){
      up_nodes[[node]]=get_upstream(clan_net,node)
    }
    end_i=end_nodes[1]
    end.nodes_added <- c(end_i)
    while(length(setdiff(end_nodes,end.nodes_added))>0){
      num.comm = unlist(lapply(up_nodes[setdiff(end_nodes,end.nodes_added)], function(x) length(intersect(up_nodes[[node_start]],x))))
      end_i=names(which.max(num.comm))
      end.nodes_added <- c(end.nodes_added,end_i)
    }
    end.nodes_xs=1:length(end_nodes)
    names(end.nodes_xs)=end.nodes_added
    
    num_branch <- apply(clan_net>0,1,sum)
    branch_nodes = names(num_branch)[which(num_branch>1)]
    if(!node_start%in%branch_nodes){
      branch_nodes=c(branch_nodes,node_start)
    }
    branch.nodes_xs=c()
    for(node in branch_nodes){
      branch_ends=intersect(get_downstream(clan_net,node),end_nodes)
      branch.nodes_xs=c(branch.nodes_xs, mean(end.nodes_xs[branch_ends]))
    }
    names(branch.nodes_xs)=branch_nodes
    for(node in branch_nodes){
      up_nodes[[node]]=get_upstream(clan_net,node)
    }
    anchor.nodes_xs=c(end.nodes_xs,branch.nodes_xs)
    nodes.added=c()
    xs.all=c()
    for(node in names(up_nodes)){
      branch_up=intersect(up_nodes[[node]],branch_nodes)
      seg_nodes=setdiff(up_nodes[[node]],unique(unlist(up_nodes[setdiff(branch_up,node)])))
      xs.all=c(xs.all,rep(as.numeric(anchor.nodes_xs[node]),length(seg_nodes)))
      nodes.added=c(nodes.added,seg_nodes)
    }
    names(xs.all)=nodes.added
    xs.all[names(branch.nodes_xs)]=branch.nodes_xs
    coords[,"x"]=xs.all[rownames(coords)]
    return(coords)
  }
}
start_nodes <- colnames(net_int_good)[which(apply(net_int_good,2,sum)==0)]
all_sub_coords=list()
num_modules=c()
for(node in start_nodes){
  all_sub_coords[[node]]=clan_coord(net_int_good,node)
  num_modules=c(num_modules,length(get_downstream(net_int_good,node)))
}
names(num_modules)=start_nodes
ordered_modules=names(sort(num_modules,decreasing = T))
combined_coords=all_sub_coords[[ordered_modules[1]]]
for(lin_ind in 2:length(ordered_modules)){
  base_coord=max(combined_coords[,"x"])+1
  coord2bind=all_sub_coords[[ordered_modules[lin_ind]]]
  coord2bind[,"x"]=coord2bind[,"x"]+base_coord
  combined_coords=rbind(combined_coords,coord2bind)
}
library(igraph)
g <- graph.adjacency(net_int_good>0)
edge_list=get.edgelist(g)

Save all information in a list

M.tree <- list(geneXmodule=allGene_allM, moduleXcell=allM_allCell, lineageXcell=lineage_cell, net_adj=net_int_good, coords=combined_coords, edge_list=edge_list, lineage_ident=all_lineages, top_genes=zf_top, ordered_stages=stages, roots=start_nodes, tips=all_end_nodes)
#saveRDS(M.tree, "./ModuleTree201809.rds")

Plot gene weights on the module tree

Notochord marker gene

plot_MTree("NOTO",M.tree)

Ectoderm marker gene

prechordal plate marker gene

endoderm marker gene

EVL marker gene

Cell cycle gene

Stress response gene

plot_MTree("FOSAB",M.tree)
LS0tCnRpdGxlOiAiQ29ubmVjdCBtb2R1bGVzIGJldHdlZW4gc3RhZ2VzIgpsaW5lc3RyZXRjaDogMC41Cm91dHB1dDoKICBwZGZfZG9jdW1lbnQ6CiAgICBsYXRleF9lbmdpbmU6IHhlbGF0ZXgKICBodG1sX25vdGVib29rOiBkZWZhdWx0CiAgaHRtbF9kb2N1bWVudDoKICAgIGNvZGVfZm9sZGluZzogaGlkZQotLS0KXGZvbnRzaXplezh9ezE4fQoKYGBge3IgcmVhZF9mdW5jdGlvbnMsIHJlc3VsdHM9J2hpZGUnLCBtZXNzYWdlPUYsIHdhcm5pbmc9Rn0Kc3VwcHJlc3NXYXJuaW5ncyhsaWJyYXJ5KCJrbml0ciIpKQpzdXBwcmVzc1dhcm5pbmdzKGxpYnJhcnkoImdwbG90cyIpKQpzdXBwcmVzc1dhcm5pbmdzKGxpYnJhcnkoImlncmFwaCIpKQpvcHRzX2NodW5rJHNldCh0aWR5Lm9wdHM9bGlzdCh3aWR0aC5jdXRvZmY9ODApLHRpZHk9VFJVRSxkZXY9InBuZyIsZHBpPTE1MCkKYGBgCgojIyBkZWZpbmUgdGhlIGZ1bmN0aW9ucyB0aGF0IHdpbGwgYmUgdXNlZCBmb3IgZXh0cmFjdGluZyB1c2VmdWwgZGF0YQpgYGB7cn0KbG9hZF9vYmogPC0gZnVuY3Rpb24oZmlsZS5wYXRoKXsKICB0ZW1wLnNwYWNlIDwtIG5ldy5lbnYoKQogIG9iajwtbG9hZChmaWxlLnBhdGgsIHRlbXAuc3BhY2UpCiAgb2JqMjwtZ2V0KG9iaiwgdGVtcC5zcGFjZSkKICBybSh0ZW1wLnNwYWNlKQogIHJldHVybihvYmoyKQp9CgptYXhTY2wgPC0gZnVuY3Rpb24oZGYsIGRpcj0ncm93JywgbWF4X3ZhbHVlPU5VTEwsIGxvZ19zcGFjZT1UUlVFKXsKICBpZihkaXI9PSdyb3cnKXsKICAgIGRpcj0xCiAgfWVsc2UgaWYoZGlyPT0nY29sJyl7CiAgICBkaXI9MgogIH1lbHNlewogICAgcHJpbnQoImRpciBtdXN0IGJlICdyb3cnIG9yICdjb2wnLiIpCiAgICByZXR1cm4KICB9CiAgaWYoaXMubnVsbChtYXhfdmFsdWUpKXsKICAgIG1heF92YWx1ZT1tZWRpYW4oYXBwbHkoZGYsZGlyLG1heCkpCiAgfQogIGlmKGxvZ19zcGFjZSl7CiAgICBkZj1leHBtMShkZikKICAgIG1heF92YWx1ZT1leHBtMShtYXhfdmFsdWUpCiAgfQogIGRmX3NjbD1zd2VlcChkZixkaXIsYXBwbHkoZGYsZGlyLG1heCksIi8iKQogIGRmX3NjbD1kZl9zY2wqbWF4X3ZhbHVlCiAgaWYobG9nX3NwYWNlKXsKICAgIGRmX3NjbD1sb2cxcChkZl9zY2wpCiAgfQogIHJldHVybihkZl9zY2wpCn0KCm1vZHVsZS5tYXRjaCA8LSBmdW5jdGlvbihOTUZfbGlzdCwgcmVmX3JlcD0ncmVwMCcsIG1pbi5jb3I9MC41LCB2ZXJib3NlPUYpewogIE5NRl9Ncz1saXN0KCkKICBOTUZfR3M9bGlzdCgpCiAgTk1GX0dzW1tyZWZfcmVwXV09bWF4U2NsKE5NRl9saXN0W1tyZWZfcmVwXV1bWyJHIl1dLGRpciA9ICdjb2wnLG1heF92YWx1ZT0xLGxvZ19zcGFjZSA9IEYpCiAgbnVtX009ZGltKE5NRl9Hc1tbcmVmX3JlcF1dKVsyXQogIG51bV9nZW49ZGltKE5NRl9Hc1tbcmVmX3JlcF1dKVsxXQogIGZvcihyZXAgaW4gc2V0ZGlmZihuYW1lcyhOTUZfbGlzdCkscmVmX3JlcCkpewogICAgICAjI21hdGNoIG1vZHVsZXMgYWNyb3NzIGRpZmZlcmVudCByZXBsaWNhdGVzCiAgICAgIG5fRz1OTUZfbGlzdFtbcmVwXV1bWydHJ11dCiAgICAgIG5fRz1tYXhTY2wobl9HLGRpciA9ICdjb2wnLG1heF92YWx1ZT0xLGxvZ19zcGFjZSA9IEYpCiAgICAgIE5NRl9Hc1tbcmVwXV09bl9HCiAgICAgIG1hdGNoX2luZD1jKCkKICAgICAgZm9yKGkgaW4gMTpudW1fTSl7CiAgICAgICAgdmVjPU5NRl9Hc1tbcmVmX3JlcF1dWyxpXQogICAgICAgIHZlY19pbmQ9d2hpY2godmVjPjAuMSkKICAgICAgICBHX2luZD13aGljaChhcHBseShuX0csMSxtYXgpPjAuMSkKICAgICAgICB1c2VfaW5kPXVuaW9uKHZlY19pbmQsR19pbmQpCiAgICAgICAgY29ycz1jb3IodmVjW3VzZV9pbmRdLG5fR1t1c2VfaW5kLF0pCiAgICAgICAgY29yX2luZD13aGljaC5tYXgoY29ycykKICAgICAgICBpZihtYXgoY29ycykgPCBtaW4uY29yKXsgIyNTSE9VTEQgUkVDT1JEIFRIRSBDT1JSRUxBVElPTiBTQ09SRVMgQU5EIFNFRSBJRiBUSEVSRSBBUkUgQU1CSUdVT1VTIE1BVENIRVMKICAgICAgICAgIG1hdGNoX2luZD1jKG1hdGNoX2luZCxOYU4pCiAgICAgICAgICAjcHJpbnQocGFzdGUoc3RhZ2UsInJlcDAgbW9kdWxlIixpLTEsImhhcyBubyBtYXRjaCBpbiIscmVwKSkKICAgICAgICAgIE5NRl9Hc1tbcmVwXV1bLGldPU5hTgogICAgICAgIH1lbHNlewogICAgICAgICAgTk1GX0dzW1tyZXBdXVssaV09bl9HWyxjb3JfaW5kXQogICAgICAgICAgbWF0Y2hfaW5kPWMobWF0Y2hfaW5kLGNvcl9pbmQpCiAgICAgICAgfQogICAgICB9CiAgICAgIGlmKHZlcmJvc2UpewogICAgICAgIGlmKG51bV9NIT1sZW5ndGgodW5pcXVlKG1hdGNoX2luZCkpKXsKICAgICAgICAgIHByaW50KHBhc3RlKHN0YWdlLHJlcCwiIG1vZHVsZXMgd2l0aCBkdXBsaWNhdGVkIG1hdGNoZXM6IikpCiAgICAgICAgICBmb3IgKGkgaW4gbWF0Y2hfaW5kW3doaWNoKGR1cGxpY2F0ZWQobWF0Y2hfaW5kKSldKXsKICAgICAgICAgICAgaWYoIWlzLm5hKGkpKXsKICAgICAgICAgICAgICBwcmludChwYXN0ZSh0b1N0cmluZyh3aGljaChtYXRjaF9pbmQ9PWkpLTEpLCAiZnJvbSByZXAwIG1hdGNoZWQgdG8iLGktMSkpCiAgICAgICAgICAgIH0KICAgICAgICAgIH0KICAgICAgICAgIHByaW50KHBhc3RlKCJtb2R1bGVzIHdpdGggbm8gbWF0Y2giLHRvU3RyaW5nKHNldGRpZmYoYygxOm51bV9NKSx1bmlxdWUobWF0Y2hfaW5kKSktMSkpKQogICAgICAgIH0KICAgICAgfQogICAgICAjTk1GX0dzW1twYXN0ZTAoIkRTIixzdGFnZSldXVtbcmVwXV09bWF4U2NsKE5NRl9Hc1tbcGFzdGUwKCJEUyIsc3RhZ2UpXV1bW3JlcF1dLGRpciA9ICdjb2wnKQogICAgICAjTk1GX3RvcHNbW3JlcF1dPU5NRl9saXN0W1tyZXBdXVtbInRvcDMwZ2VuZXMiXV0KICAgIH0KICBudW1fcmVwcz1sZW5ndGgobmFtZXMoTk1GX2xpc3QpKQogIGZvcihtIGluIGNvbG5hbWVzKE5NRl9Hc1tbcmVmX3JlcF1dKSl7CiAgICBOTUZfTXNbW21dXT1tYXRyaXgobnJvdz1udW1fZ2VuLG5jb2wgPSBudW1fcmVwcykKICAgIHJvd25hbWVzKE5NRl9Nc1tbbV1dKT1yb3duYW1lcyhOTUZfR3NbW3JlZl9yZXBdXSkKICAgIGNvbG5hbWVzKE5NRl9Nc1tbbV1dKT1wYXN0ZTAoInJlcCIsYygwOihudW1fcmVwcy0xKSkpCiAgICBmb3IocmVwIGluIG5hbWVzKE5NRl9saXN0KSl7CiAgICAgIE5NRl9Nc1tbbV1dWyxyZXBdPU5NRl9Hc1tbcmVwXV1bLG1dCiAgICB9CiAgICBtYXhfdz1hcHBseShOTUZfTXNbW21dXSwxLCBmdW5jdGlvbih4KSBtYXgoeCxuYS5ybSA9IFQpKQogICAgI21pbl93PWFwcGx5KE5NRl9Nc1tbcGFzdGUwKCJEUyIsc3RhZ2UpXV1bW3Bhc3RlMCgiTW9kdWxlIixtKV1dLDEsbWluKQogICAgTk1GX01zW1ttXV09Tk1GX01zW1ttXV1bLXdoaWNoKG1heF93PDAuMSksICxkcm9wPUZdCiAgICByZV9pbmQ9b3JkZXIoTk1GX01zW1ttXV1bLHJlZl9yZXBdLGRlY3JlYXNpbmcgPSBUKQogICAgTk1GX01zW1ttXV09Tk1GX01zW1ttXV1bcmVfaW5kLF0KICAgICNwcmludChwYXN0ZSgiTW9kdWxlIixtLCIjIGtlcHQgZ2VuZXM6IixkaW0oTk1GX01zW1twYXN0ZTAoIkRTIixzdGFnZSldXVtbcGFzdGUwKCJNb2R1bGUiLG0pXV0pWzFdKSkKICB9CiAgcmV0dXJuKE5NRl9NcykKfQpgYGAKCgojIExvYWQgdGhlIE5NRiByZXN1bHRzIGZvciBlYWNoIHN0YWdlICh0aGVzZSBkYXRhIGZpbGVzIGFyZSBub3QgcHJvdmlkZWQgZHVlIHRvIHRoZWlyIGxhcmdlIHNpemVzKQpBIGJlc3QgSyAobnVtYmVyIG9mIG1vZHVsZXMgb3IgYG5fY29tcG9uZW50YCBhcmd1bWVudCB1c2VkIGZvciBydW5uaW5nIE5NRikgaXMgcGlja2VkIGZvciBlYWNoIHN0YWdlIGJhc2VkIG9uIHRoZSBzdGFiaWxpdHkgb2YgdGhlIHJlc3VsdHMgZnJvbSAxMCBOTUYgcnVucyB3aXRoIHJhbmRvbSBpbml0aWFsIGNvbmRpdGlvbnMuIAoKYGBge3J9ClpGSElHSF9rPWMoMTApClpGT0JMT05HX2s9YygxMSkKWkZET01FX2s9YygxNykKWkYzMF9rPWMoMTUpClpGNTBfaz1jKDIwKQpaRlNfaz1jKDI1KQpaRjYwX2s9YygyNSkKWkY3NV9rPWMoMjQpClpGOTBfaz1jKDQ1KQpaRkJfaz1jKDQwKQpaRjNTX2s9YygzMSkKWkY2U19rPWMoNDIpCgpzdGFnZXM9YygiWkZISUdIIiwiWkZPQkxPTkciLCJaRkRPTUUiLCJaRjMwIiwiWkY1MCIsIlpGUyIsIlpGNjAiLCJaRjc1IiwiWkY5MCIsIlpGQiIsIlpGM1MiLCJaRjZTIikKCnpmX0M8LWxpc3QoKQp6Zl9HPC1saXN0KCkKemZfdG9wIDwtIGxpc3QoKQp6Zl9nZW5lcz1jKCkKTk1GX2xpc3Q9bGlzdCgpCm1vZHVsZV9tYXRjaD1saXN0KCkKZm9yKHN0YWdlIGluIHN0YWdlcyl7CiAgc3RhZ2Vfaz1nZXQocGFzdGUwKHN0YWdlLCJfayIpKVsxXQogIE5NRl9vYmo9bG9hZF9vYmoocGFzdGUwKCJ+L0Ryb3Bib3gvRGVza3RvcF9MYXB0b3AvRGF0YSBhbmQgYW5hbHlzaXMvRmluYWwgc2NyaXB0cy9OTUYvUmVzdWx0cy9EU19zdGFnZXMvRFNfIixzdGFnZSwiL3Jlc3VsdF90YmxzLlJvYmoiKSkKICBOTUZfbGlzdFtbc3RhZ2VdXT1OTUZfb2JqW1twYXN0ZTAoIks9IixzdGFnZV9rKV1dW1sicmVwMCJdXQogIHpmX0NbW3N0YWdlXV09ZGF0YS5mcmFtZShOTUZfbGlzdFtbc3RhZ2VdXVtbIkMiXV0sIHN0cmluZ3NBc0ZhY3RvcnMgPSBGKQogIHpmX0dbW3N0YWdlXV09ZGF0YS5mcmFtZShOTUZfbGlzdFtbc3RhZ2VdXVtbIkciXV0sIHN0cmluZ3NBc0ZhY3RvcnMgPSBGKQogIGNvbG5hbWVzKHpmX0dbW3N0YWdlXV0pPXJvd25hbWVzKHpmX0NbW3N0YWdlXV0pCiAgemZfZ2VuZXM9Yyh6Zl9nZW5lcywgcm93bmFtZXMoemZfR1tbc3RhZ2VdXSkpCiAgemZfdG9wW1tzdGFnZV1dPWRhdGEuZnJhbWUoTk1GX2xpc3RbW3N0YWdlXV1bWyJ0b3AzMGdlbmVzIl1dLCBzdHJpbmdzQXNGYWN0b3JzID0gRikKICBtb2R1bGVfbWF0Y2hbW3N0YWdlXV09bW9kdWxlLm1hdGNoKE5NRl9vYmpbW3Bhc3RlMCgiSz0iLHN0YWdlX2spXV0sIHJlZl9yZXA9J3JlcDAnLG1pbi5jb3I9MC41KQp9CmBgYAoKCiMgRmluZCBhbmQgcmVtb3ZlIG1vZHVsZXMgdGhhdCBhcmUgcHJpbWFyaWx5IGRyaXZlbiBieSBiYXRjaCBhbmQgbm9pc2UgZnJvbSBlYWNoIHN0YWdlCkJhdGNoIG1vZHVsZXMgYXJlIGZvdW5kIHVzaW5nIHRoZSBgQmF0Y2hHZW5lYCBmdW5jdGlvbiBpbiAqU2V1cmF0KiBwYWNrYWdlLiBOb2lzZSBtb2R1bGVzIGFyZSBkZWZpbmVkIGFzIHRoZSBvbmVzIHRoYXQgYXJlIHByaW1hcmlseSBkcml2ZW4gYnkgYSBzaW5nbGUgZ2VuZSAodGhlIHRvcCByYW5rZWQgZ2VuZSBoYXMgYSB3ZWlnaHQgbW9yZSB0aGFuIDMgdGltZXMgdGhlIHdlaWdodCBvZiB0aGUgc2Vjb25kIHJhbmtlZCBnZW5lKS4KYGBge3J9CmxpYnJhcnkoIlNldXJhdCIpCnJtQnlDZWxsIDwtIGZ1bmN0aW9uKHNjRGF0YSxsb3c9MSl7CiAgYkRhdGE9c2NEYXRhPjAKICAjc3VtIHVwIGVhY2ggcm93IGluIHRoZSBiaW5hcnkgbWF0cml4IGZvciBjZWxsIG51bWJlcnMKICBudW0uY2VsbD1hcHBseShiRGF0YSwxLHN1bSkKICBybS5pbmQ9d2hpY2gobnVtLmNlbGw8PWxvdykKICBzY0RhdGEuZj1zY0RhdGEKICAjcHJpbnQocGFzdGUoInJlbW92aW5nIixsZW5ndGgocm0uaW5kKSwiZ2VuZXMuLi4iKSkKICBpZiAobGVuZ3RoKHJtLmluZCk+MCl7CiAgICBzY0RhdGEuZj1zY0RhdGFbLXJtLmluZCxdCiAgfQogICNub3cgdGhlcmUgY291bGQgYmUgY2VsbHMgd2l0aCBubyBnZW5lIGRldGVjdGlvbi4gcmVtb3ZlIHRoZW0KICBybUJ5R2VuZXMoc2NEYXRhLmYsbG10PTApCiAgcmV0dXJuKHNjRGF0YS5mKQp9CgpybUJ5R2VuZXMgPC0gZnVuY3Rpb24oc2NEYXRhLGxtdCl7CiAgI2ZpcnN0IGNyZWF0IGEgYmluYXJ5IG1hdHJpeCBmb3IgZ2VuZSBkZXRlY3Rpb24KICBjcHRyPXNjRGF0YT4wCiAgI3RoZW4gc3VtIHVwIGVhY2ggY29sdW1uIGluIHRoZSBiaW5hcnkgbWF0cml4IGZvciBnZW5lIG51bWJlcnMKICBudW0uY3B0cj1hcHBseShjcHRyLDIsc3VtKQogIHJtLmluZD13aGljaChudW0uY3B0cjw9bG10KQogIHNjRGF0YS5mPXNjRGF0YQogIGlmIChsZW5ndGgocm0uaW5kKT4wKXsKICAgICNwcmludChwYXN0ZSgicmVtb3ZpbmciLGxlbmd0aChybS5pbmQpLCJjZWxscyB3aXRoIGZld2VyIHRoYW4iLGxtdCwiZ2VuZXMuLi4iKSkKICAgIHNjRGF0YS5mPXNjRGF0YVssLXJtLmluZF0KICB9CiAgI25vdyB0aGVyZSBjb3VsZCBiZSBnZW5lcyB3aXRoIG5vIGRldGVjdGlvbiBpbiBhbnkgY2VsbHMuIHJlbW92ZSB0aGVtCiAgY3B0cj1zY0RhdGEuZj4wCiAgbnVtLmNlbGw9YXBwbHkoY3B0ciwxLHN1bSkKICBybS5pbmQ9d2hpY2gobnVtLmNlbGw9PTApCiAgaWYgKGxlbmd0aChybS5pbmQpPjApewogICAgc2NEYXRhLmY9c2NEYXRhLmZbLXJtLmluZCxdCiAgfQogIHJldHVybihzY0RhdGEuZikKfQoKZmlsdGVyLm1vZHVsZXMgPC0gZnVuY3Rpb24oemZfQywgemZfRywgYmF0Y2gucm09VCwgYmF0Y2guZmllbGQ9MSwgbm9pcy5yYXQ9MywgYmF0Y2guY3V0b2ZmPTAuNzUsIHZlcmJvc2U9VCwgbW9kdWxlX21hdGNoPU5VTEwpewogIHN0YWdlcz1uYW1lcyh6Zl9DKQogIHpmX0NfdXNlPWxpc3QoKQogIHpmX0dfdXNlPWxpc3QoKQogIG1vZHVsZV9tYXRjaF91c2U9bGlzdCgpCiAgZm9yKHN0YWdlIGluIHN0YWdlcyl7CiAgICBiYXRjaF9tb2R1bGU9YygpCiAgICBpZihiYXRjaC5ybSl7CiAgICAgIFpGX3NldXJhdD1uZXcoInNldXJhdCIscmF3LmRhdGE9emZfQ1tbc3RhZ2VdXSkKICAgICAgI29yaWdpbmFsOiBaRl9zZXVyYXQ9U2V0dXAoWkZfc2V1cmF0LHByb2plY3Q9ImRzIixtaW4uY2VsbHMgPSAyLCBuYW1lcy5maWVsZCA9IDMsbmFtZXMuZGVsaW0gPSAiXyIsZG8ubG9nTm9ybWFsaXplID0gRixpcy5leHByID0gMC4wMSxtaW4uZ2VuZXMgPSAxKQogICAgICBaRl9zZXVyYXQ9Q3JlYXRlU2V1cmF0T2JqZWN0KHpmX0NbW3N0YWdlXV0scHJvamVjdD0iZHMiLG1pbi5jZWxscyA9IDIsIG5hbWVzLmZpZWxkID0gYmF0Y2guZmllbGQsbmFtZXMuZGVsaW0gPSAiXyIsaXMuZXhwciA9IDAuMDEsbWluLmdlbmVzID0gMikgI2RvLmxvZ05vcm1hbGl6ZSA9IEYsCiAgICAgICNvcmlnaW5hbDogY3V0X29mZj0wLjczCiAgICAgICMgY3V0X29mZj0wLjcyCiAgICAgICMgaWYoc3RhZ2UgJWluJSBjKCJCIikpewogICAgICAjICAgY3V0X29mZj0wLjc1CiAgICAgICMgfQogICAgICBiYXRjaC5mcmFjPXVubGlzdChsYXBwbHkobGV2ZWxzKFpGX3NldXJhdEBpZGVudCksIGZ1bmN0aW9uKHgpIHN1bShaRl9zZXVyYXRAaWRlbnQ9PXgpL2xlbmd0aChaRl9zZXVyYXRAaWRlbnQpKSkKICAgICAgYmF0Y2gudXNlPWxldmVscyhaRl9zZXVyYXRAaWRlbnQpW3doaWNoKGJhdGNoLmZyYWM+MC4xKV0KICAgICAgYmF0Y2hfbW9kdWxlPUJhdGNoR2VuZShaRl9zZXVyYXQsaWRlbnRzLnVzZT1iYXRjaC51c2UsZ2VuZXMudXNlPXJvd25hbWVzKFpGX3NldXJhdEBkYXRhKSxhdWMuY3V0b2ZmID0gYmF0Y2guY3V0b2ZmKQogICAgICBpZih2ZXJib3NlKXsKICAgICAgICBwcmludChwYXN0ZSgiU3RhZ2U6Iiwgc3RhZ2UpKQogICAgICAgIHByaW50KHBhc3RlKCJudW1iZXIgb2YgYmF0Y2hlczoiLCBsZW5ndGgoYmF0Y2gudXNlKSkpCiAgICAgICAgcHJpbnQoYmF0Y2guZnJhYykKICAgICAgICBwcmludCgiQmF0Y2ggbW9kdWxlczoiKQogICAgICAgIHByaW50KGJhdGNoX21vZHVsZSkKICAgICAgfQogICAgfQogICAgd2VpZ2hfc3Q9YXBwbHkoemZfR1tbc3RhZ2VdXSwyLHNvcnQpCiAgICB3ZWlnaF9yYXQ9d2VpZ2hfc3RbZGltKHdlaWdoX3N0KVsxXSxdL3dlaWdoX3N0W2RpbSh3ZWlnaF9zdClbMV0tMSxdCiAgICBub2lzPXdlaWdoX3JhdFt3aGljaCh3ZWlnaF9yYXQ+bm9pcy5yYXQpXQogICAgaWYobGVuZ3RoKG5vaXMpPjAgJiYgdmVyYm9zZSl7CiAgICAgIHByaW50KCJOb2lzZSBtb2R1bGVzOiIpCiAgICAgIHByaW50KG5hbWVzKG5vaXMpKQogICAgfQogICAgYmF0Y2hfbW9kdWxlPXVuaW9uKGJhdGNoX21vZHVsZSxuYW1lcyhub2lzKSkKICAgIHpmX0NfdXNlW1tzdGFnZV1dIDwtIHpmX0NbW3N0YWdlXV1bc2V0ZGlmZihyb3duYW1lcyh6Zl9DW1tzdGFnZV1dKSxiYXRjaF9tb2R1bGUpLF0KICAgIHpmX0NfdXNlW1tzdGFnZV1dIDwtIG1heFNjbCh6Zl9DX3VzZVtbc3RhZ2VdXSxtYXhfdmFsdWUgPSAxLCBsb2dfc3BhY2U9RikKICAgIHpmX0dfdXNlW1tzdGFnZV1dIDwtIHpmX0dbW3N0YWdlXV1bLHNldGRpZmYoY29sbmFtZXMoemZfR1tbc3RhZ2VdXSksYmF0Y2hfbW9kdWxlKV0KICAgIHpmX0dfdXNlW1tzdGFnZV1dIDwtIHJtQnlDZWxsKHpmX0dfdXNlW1tzdGFnZV1dLGxvdyA9IDApCiAgICB6Zl9HX3VzZVtbc3RhZ2VdXSA8LSBtYXhTY2woemZfR191c2VbW3N0YWdlXV0sbWF4X3ZhbHVlID0gMSwgZGlyID0gJ2NvbCcsbG9nX3NwYWNlID0gRikKICAgIGlmKCFpcy5udWxsKG1vZHVsZV9tYXRjaCkpewogICAgICBtb2R1bGVfbWF0Y2hfdXNlW1tzdGFnZV1dIDwtIG1vZHVsZV9tYXRjaFtbc3RhZ2VdXVtzZXRkaWZmKG5hbWVzKG1vZHVsZV9tYXRjaFtbc3RhZ2VdXSkscGFzdGUwKCJYIixiYXRjaF9tb2R1bGUpKV0KICAgIH0KICB9CiAgaWYoaXMubnVsbChtb2R1bGVfbWF0Y2gpKXsKICAgIHJldHVybihsaXN0KEM9emZfQ191c2UsRz16Zl9HX3VzZSkpCiAgfWVsc2V7CiAgICByZXR1cm4obGlzdChDPXpmX0NfdXNlLEc9emZfR191c2UsbWF0Y2g9bW9kdWxlX21hdGNoX3VzZSkpCiAgfQp9CnpmX3VzZSA9IGZpbHRlci5tb2R1bGVzKHpmX0MsemZfRyxtb2R1bGVfbWF0Y2ggPSBtb2R1bGVfbWF0Y2gsIGJhdGNoLmN1dG9mZiA9IDAuNzE1LCBiYXRjaC5maWVsZCA9IDMsIHZlcmJvc2UgPSBGKQpgYGAKCiMjIyBQcmludCBvdXQgdGhlIHNpemUgb2YgbWF0cml4IEcgYXQgZWFjaCBzdGFnZSAod2Ugd2lsbCB1c2UgdGhlc2UgbWF0cmljZXMgdG8gYnVpbGQgdGhlIHRyZWUgb2YgY29ubmVjdGVkIG1vZHVsZXMpCmBgYHtyfQpmb3Ioc3RhZ2UgaW4gc3RhZ2VzKXsKICBwcmludChzdGFnZSkKICBwcmludChkaW0oemZfdXNlW1siRyJdXVtbc3RhZ2VdXSkpCn0KYGBgCgojIEZpZ3VyZSBvdXQgaG93IG1hbnkgdG9wIGdlbmVzIHRvIHVzZSBmb3IgY2FsY3VsYXRpbmcgb3ZlcmxhcCBzY29yZXMKRm9yIGVhY2ggc3RhZ2UsIGNhbGN1bGF0ZSB0aGUgY29lZmZpY2llbnQgb2YgdmFyaWFuY2UgKENWKSBhbmQgYSAnc3BlY2lmaWNpdHkgc2NvcmUnIGZvciBlYWNoIGdlbmUncyB3ZWlnaHQgaW4gZWFjaCBtb2R1bGUgYWNyb3NzIHRoZSAxMCByZXBsaWNhdGlvbnMuIFRvIGNhbGN1bGF0ZSB0aGUgQ1Ygb2YgYSBnZW5lIGluIGEgcGFydGljdWxhciBtb2R1bGUsIHdlIGZpcnN0IGV4dHJhY3QgdGhhdCBtb2R1bGUgZnJvbSBlYWNoIG9mIHRoZSAxMCBOTUYgcnVucyAobW9kdWxlcyBhcmUgbWF0Y2hlZCBieSBjb3JyZWxhdGlvbiBvZiBnZW5lIHdlaWd0aHMpLiBUaGVuIHRoZSBDViBvZiBhIGdlbmUgaW4gdGhpcyBtb2R1bGUgaXMgZGVmaW5lZCBhcyB0aGUgbWVhbiBvZiBpdHMgd2VpZ2h0cyBkaXZpZGVkIGJ5IHRoZSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgaXRzIHdlaWdodHMgYWNyb3NzIHRoZXNlIDEwIHJlcGxpY2F0aW9ucy4gVGhlIHNwZWNpZmljaXR5IHNjb3JlIG9mIGEgZ2VuZSBmb3IgYSBtb2R1bGUgaXMgY2FsY3VsYXRlZCBhcyB0aGUgd2VpZ2h0IG9mIHRoZSBnZW5lIGluIHRoYXQgbW9kdWxlIGRpdmlkZWQgYnkgdGhlIHN1bSBvZiB0aGUgZ2VuZSdzIHdlaWdodHMgaW4gYWxsIG1vZHVsZXMgZnJvbSB0aGUgc2FtZSBydW4uCklmIGEgZ2VuZSBpcyBhICdyb2J1c3QnIG1hcmtlciBvZiB0aGUgbW9kdWxlLCBpdCBzaG91bGQgaGF2ZSBhIHNtYWxsIENWIGFuZCBhIGhpZ2ggc3BlY2lmaWNpdHkuIFdlIHRoZW4gcGxvdCB0aGVzZSBzdGF0aXN0aWNzIG9mIHRoZSB0b3AgcmFua2luZyBnZW5lcyBpbiBlYWNoIG1vZHVsZSB0byBzZWUgd2hlbiBDViBiZWNvbWVzIGhpZ2ggYW5kIHNwZWNpZmljaXR5IGJlY29tZXMgbG93LCBpbmRpY2F0aW5nIHRoZSBnZW5lcyByYW5rZWQgaGlnaGVyIHRoYW4gdGhhdCBhcmUgZ29vZCBnZW5lcyB0byB1c2UgaW4gdGhlIG92ZXJsYXAgc2NvcmUgY2FsY3VsYXRpb25zLgpgYGB7cn0Kd2VpZ2h0X2N2PWxpc3QoKQpmb3Ioc3RhZ2UgaW4gbmFtZXMoemZfdXNlJG1hdGNoKSl7CiAgI251bV9nZW49bWluKHVubGlzdChsYXBwbHkoemZfdXNlJG1hdGNoW1tzdGFnZV1dLCBmdW5jdGlvbih4KSBkaW0oeClbMV0pKSkKICBudW1fZ2VuPTQwCiAgd2VpZ2h0X2N2W1tzdGFnZV1dPW1hdHJpeChucm93PW51bV9nZW4sIG5jb2wgPSBsZW5ndGgoemZfdXNlJG1hdGNoW1tzdGFnZV1dKSkKICBjb2xuYW1lcyh3ZWlnaHRfY3ZbW3N0YWdlXV0pPW5hbWVzKHpmX3VzZSRtYXRjaFtbc3RhZ2VdXSkKICBmb3IobSBpbiBuYW1lcyh6Zl91c2UkbWF0Y2hbW3N0YWdlXV0pKXsKICAgIG51bV92YWwgPSBtaW4obnVtX2dlbixkaW0oemZfdXNlJG1hdGNoW1tzdGFnZV1dW1ttXV0pWzFdKQogICAgd2VpZ2h0X2N2W1tzdGFnZV1dWzE6bnVtX3ZhbCxtXT1hcHBseSh6Zl91c2UkbWF0Y2hbW3N0YWdlXV1bW21dXVsxOm51bV92YWwsXSwgMSwgZnVuY3Rpb24oeCkgc3FydCh2YXIoeCxuYS5ybSA9IFQpKS9tZWFuKHgsIG5hLnJtPVQpKQogIH0KfQoKd2VpZ2h0X3NwZWM9bGlzdCgpCmZvcihzdGFnZSBpbiBuYW1lcyh6Zl91c2UkbWF0Y2gpKXsKICB3ZWlnaHRfc3BlY1tbc3RhZ2VdXT16Zl91c2UkR1tbc3RhZ2VdXQogIHJvd25hbWVzKHdlaWdodF9zcGVjW1tzdGFnZV1dKT0xOmRpbSh6Zl91c2UkR1tbc3RhZ2VdXSlbMV0KICB3ZWlnaHRfc3BlY1tbc3RhZ2VdXT1zd2VlcCh3ZWlnaHRfc3BlY1tbc3RhZ2VdXSwxLGFwcGx5KHpmX3VzZSRHW1tzdGFnZV1dLDEsc3VtKSwiLyIpCiAgZm9yKGkgaW4gMTpkaW0oemZfdXNlJEdbW3N0YWdlXV0pWzJdKXsKICAgIGluZF9pPW9yZGVyKHpmX3VzZSRHW1tzdGFnZV1dWyxpXSxkZWNyZWFzaW5nID0gVCkKICAgIHdlaWdodF9zcGVjW1tzdGFnZV1dWyxpXT13ZWlnaHRfc3BlY1tbc3RhZ2VdXVtpbmRfaSxpXQogIH0KfQpwYXIobWZyb3c9YygzLDIpKQpmb3Ioc3RhZ2UgaW4gbmFtZXMod2VpZ2h0X2N2KSl7CiAgI3Bsb3QoMTpkaW0od2VpZ2h0X2N2W1tzdGFnZV1dKVsxXSxhcHBseSh3ZWlnaHRfY3ZbW3N0YWdlXV0sMSxmdW5jdGlvbih4KSBtZWFuKHgsbmEucm09VCkpLG1haW49c3RhZ2UsIHlsYWI9Ik1lYW4gQ1YiLHhsYWI9IlJhbmsiKQogICNwbG90KDE6NDAsYXBwbHkod2VpZ2h0X3NwZWNbW3N0YWdlXV1bMTo0MCxdLDEsZnVuY3Rpb24oeCkgbWVhbih4LG5hLnJtPVQpKSxtYWluPXN0YWdlLCB5bGFiPSJNZWFuIFNwZWNpZmljaXR5Iix4bGFiPSJSYW5rIikKICBwbG90KDE6ZGltKHdlaWdodF9jdltbc3RhZ2VdXSlbMV0sYXBwbHkod2VpZ2h0X2N2W1tzdGFnZV1dLDEsZnVuY3Rpb24oeCkgbWVkaWFuKHgsbmEucm09VCkpLG1haW49c3RhZ2UsIHlsYWI9Ik1lZGlhbiBDViIseGxhYj0iUmFuayIpCiAgcGxvdCgxOjQwLGFwcGx5KHdlaWdodF9zcGVjW1tzdGFnZV1dWzE6NDAsXSwxLGZ1bmN0aW9uKHgpIG1lZGlhbih4LG5hLnJtPVQpKSxtYWluPXN0YWdlLCB5bGFiPSJNZWRpYW4gU3BlY2lmaWNpdHkiLHhsYWI9IlJhbmsiKQp9CmBgYAoKCiMgQ2FsY3VsYXRlIHRoZSB3ZWlnaHRlZCBvdmVybGFwIGJldHdlZW4gcGFpcnMgb2YgZ2VuZSBtb2R1bGVzIGluIGFkamFjZW50IHN0YWdlcwpXZSBkZWNpZGVkIHRvIHVzZSB0aGUgdG9wIDI1IGdlbmVzIGluIGVhY2ggbW9kdWxlIGluIHRoaXMgY2FsY3VsYXRpb24uIFRoZSBvdmVybGFwIG9mIHR3byBtb2R1bGVzIGlzIGNhbGN1bGF0ZWQgYXMgdGhlIHN1bSBvZiB0aGUgd2VpZ2h0cyBvZiBzaGFyZWQgZ2VuZXMgZGl2aWRlZCBieSB0aGUgc3VtIG9mIHdlaWdodHMgb2YgYWxsIGdlbmVzLiBUaGUgcmVzdWx0cyBvZiB0aGUgb3ZlcmxhcCBzY29yZXMgYXJlIHZpc3VhbGl6ZWQgaW4gaGVhdCBtYXBzLgoKYGBge3IsZmlnLmhlaWdodD00LCBmaWcud2lkdGg9N30KV2VpZ2hfaW50ZXJzZWN0IDwtIGZ1bmN0aW9uKE0uaW5kLERhdGExLERhdGEyLG51bUdlbmUsbm9ybS5zdW09Ril7CiAgaT1NLmluZFsxXQogIGo9TS5pbmRbMl0KICBEYXRhMU09RGF0YTFbLGksZHJvcD1GXQogIERhdGEyTT1EYXRhMlssaixkcm9wPUZdCiAgdG9wR2VuZXMxPXJvd25hbWVzKERhdGExKVtvcmRlcihEYXRhMU0sZGVjcmVhc2luZz1UKVsxOm51bUdlbmVdXQogIHRvcEdlbmVzMj1yb3duYW1lcyhEYXRhMilbb3JkZXIoRGF0YTJNLGRlY3JlYXNpbmc9VClbMTpudW1HZW5lXV0KICBpZihub3JtLnN1bSl7CiAgICBEYXRhMU09RGF0YTFNL3N1bShEYXRhMU0pCiAgICBEYXRhMk09RGF0YTJNL3N1bShEYXRhMk0pCiAgfQogIGludGVyX2dlbmVzPWludGVyc2VjdCh0b3BHZW5lczEsdG9wR2VuZXMyKQogIHdlaWdodGVkX2ludGVyPShzdW0oRGF0YTFNW2ludGVyX2dlbmVzLF0pK3N1bShEYXRhMk1baW50ZXJfZ2VuZXMsXSkpLyhzdW0oRGF0YTFNW3RvcEdlbmVzMSxdKStzdW0oRGF0YTJNW3RvcEdlbmVzMixdKSkKICByZXR1cm4od2VpZ2h0ZWRfaW50ZXIpCn0KQ2FsY19pbnRlcnNlY3QgPC0gZnVuY3Rpb24oRGF0YTEsRGF0YTIsbnVtX3RvcD0yNSx3ZWlnaD1GLCBub3JtLnN1bT1GKXsKICBEYXRhMT1zd2VlcChEYXRhMSwyLGFwcGx5KERhdGExLDIsbWF4KSwnLycpCiAgRGF0YTI9c3dlZXAoRGF0YTIsMixhcHBseShEYXRhMiwyLG1heCksJy8nKQoKICBudW0uc3BsMT1kaW0oRGF0YTEpWzJdCiAgbnVtLnNwbDI9ZGltKERhdGEyKVsyXQogIGNvci5NPW1hdHJpeCgwLG5yb3c9bnVtLnNwbDIsbmNvbD1udW0uc3BsMSkKICBudW0uaW5kPW51bS5zcGwxKm51bS5zcGwyCiAgTS5pbmQ9dmVjdG9yKCJsaXN0IixsZW5ndGg9bnVtLmluZCkKICBrPTEKICBmb3IgKGkgaW4gMTpudW0uc3BsMSl7CiAgICBmb3IgKGogaW4gMTpudW0uc3BsMikgewogICAgICBNLmluZFtba11dPWMoaSxqKQogICAgICBrPWsrMQogICAgfQogIH0KCiAgaWYod2VpZ2gpewogICAgY29yLk0udmVjPWxhcHBseSgxOm51bS5pbmQsIGZ1bmN0aW9uKHgpIFdlaWdoX2ludGVyc2VjdChNLmluZFtbeF1dLERhdGExLERhdGEyLG51bV90b3AsIG5vcm0uc3VtPW5vcm0uc3VtKSkKICB9ZWxzZXsKICAgIGNvci5NLnZlYz1sYXBwbHkoMTpudW0uaW5kLCBmdW5jdGlvbih4KSBsZW5ndGgoaW50ZXJzZWN0KHJvd25hbWVzKERhdGExKVtvcmRlcihEYXRhMVssTS5pbmRbW3hdXVsxXV0sZGVjcmVhc2luZz1UKVsxOm51bV90b3BdXSxyb3duYW1lcyhEYXRhMilbb3JkZXIoRGF0YTJbLE0uaW5kW1t4XV1bMl1dLGRlY3JlYXNpbmc9VClbMTpudW1fdG9wXV0pKS9udW1fdG9wKQogIH0KCiAgZm9yIChpIGluIDE6bnVtLmluZCl7CiAgICBpbmQxPU0uaW5kW1tpXV1bMV0KICAgIGluZDI9TS5pbmRbW2ldXVsyXQogICAgY29yLk1baW5kMixpbmQxXT11bmxpc3QoY29yLk0udmVjW2ldKQogIH0KICBjb3JERj1kYXRhLmZyYW1lKGNvci5NLHJvdy5uYW1lcyA9Y29sbmFtZXMoRGF0YTIpKQogIGNvbG5hbWVzKGNvckRGKT1jb2xuYW1lcyhEYXRhMSkKICByZXR1cm4oY29yREYpCn0KCm1vZHVsZS5vdmVybGFwIDwtIGZ1bmN0aW9uKERTX0dfdXNlLCBudW0udG9wPTI1LCB3ZWlnaD1ULCBoZWF0bWFwPVQsIG5vcm0uc3VtPUYpewogIHN0YWdlcz1uYW1lcyhEU19HX3VzZSkKICBHX2ludCA8LSBsaXN0KCkKICBmb3IoaSBpbiAxOihsZW5ndGgoc3RhZ2VzKS0xKSl7CiAgICBzdGFnZT1zdGFnZXNbaV0KICAgIHN0YWdlX25leHQ9c3RhZ2VzW2krMV0KICAgICNnZW5lX3VzZT1pbnRlcnNlY3Qocm93bmFtZXMoRFNfR191c2VbW3N0YWdlXV0pLHJvd25hbWVzKERTX0dfdXNlW1tzdGFnZV9uZXh0XV0pKQogICAgR19zdGFnZT1EU19HX3VzZVtbc3RhZ2VdXQogICAgI0dfc3RhZ2U9RFNfR191c2VbW3N0YWdlXV1bZ2VuZV91c2UsXQogICAgR19zdGFnZV9uZXh0PURTX0dfdXNlW1tzdGFnZV9uZXh0XV0KICAgICNHX3N0YWdlX25leHQ9RFNfR191c2VbW3N0YWdlX25leHRdXVtnZW5lX3VzZSxdCiAgICBudW1fbW9kdWxlPWRpbShHX3N0YWdlKVsyXQogICAgbnVtX21vZHVsZV9uZXh0PWRpbShHX3N0YWdlX25leHQpW1syXV0KICAgIEdfaW50W1tzdGFnZV1dIDwtIENhbGNfaW50ZXJzZWN0KEdfc3RhZ2UsR19zdGFnZV9uZXh0LG51bV90b3AgPSBudW0udG9wLCB3ZWlnaCA9IHdlaWdoLCBub3JtLnN1bT1ub3JtLnN1bSkgCiAgICAjI3JldHVybnMgb3ZlcmxhcCBzY29yZXMgaW4gYSBtYXRyaXgsIGNvbG5hbWVzIGFyZSBtb2R1bGVzIGF0IHRoaXMgc3RhZ2UsIHJvd25hbWVzIGFyZSBtb2R1bGVzIGF0IG5leHQgc3RhZ2UKICAgIGlmKGhlYXRtYXApewogICAgICB4dmFsIDwtIGZvcm1hdEMoYXMubWF0cml4KEdfaW50W1tzdGFnZV1dKSwgZm9ybWF0PSJmIiwgZGlnaXRzPTIpCiAgICAgIGhlYXRtYXAuMihhcy5tYXRyaXgoR19pbnRbW3N0YWdlXV0pLCBSb3d2PUZBTFNFLCBDb2x2PUZBTFNFLCBkZW5kcm9ncmFtPSJub25lIiwgeGxhYj1zdGFnZSwgeWxhYj1zdGFnZV9uZXh0LCB0cmFjZT0ibm9uZSIsIGNlbGxub3RlPXh2YWwsIG5vdGVjb2w9ImJsYWNrIixub3RlY2V4PTAuNSkKICAgIH0KICB9CiAgcmV0dXJuKEdfaW50KQp9CgpHX2ludCA9IG1vZHVsZS5vdmVybGFwKHpmX3VzZVtbIkciXV0sIG51bS50b3A9MjUsIHdlaWdoPVQsIGhlYXRtYXA9VCwgbm9ybS5zdW09RikKYGBgCgojIENhbGN1bGF0ZSBvdmVybGFwIGJldHdlZW4gbW9kdWxlcyBpbiBldmVyeSBvdGhlciBzdGFnZQpJZiBhIHN0YWdlIHdhcyBub3QgZGVlcGx5IG9yIGNvbXByZWhlbnNpdmVseSBzYW1wbGVkIGFuZCBzZXF1ZW5jZWQsIHdlIG1pZ2h0IG5vdCBiZSBhYmxlIHRvIHJlY292ZXIgY2VydGFpbiBtb2R1bGVzIGZyb20gdGhhdCBzdGFnZS4gVGhpcyBjb3VsZCBwb3RlbnRpYWxseSBjcmVhdGUgZGlzLWNvbm5lY3Rpb25zIGluIHRoZSBtb2R1bGUgbGluZWFnZXMuIEluIG9yZGVyIHRvIHByb2R1Y2UgY29udGludW91cyBtb2R1bGUgbGluZWFnZXMgd2hlbiB0aGVyZSBpcyBwb3RlbnRpYWwgb2NjYXNpb25hbCBkcm9wLW91dCBvZiBtb2R1bGVzLCB3ZSBhbGxvdyBtb2R1bGVzIHNlcGFyYXRlZCBieSBvbmUgc3RhZ2UgdG8gY29ubmVjdCB0byBlYWNoIG90aGVyIHdoZW4gY29ubmVjdGlvbiB0byBpbW1lZGlhdGUgbmVpZ2hib3VyaW5nIHN0YWdlIGlzIG5vdCBmb3VuZC4KCmBgYHtyLGZpZy5oZWlnaHQ9NCwgZmlnLndpZHRoPTd9Cm1vZHVsZS5vdmVybGFwMiA8LSBmdW5jdGlvbihEU19HX3VzZSwgbnVtLnRvcD0yNSwgd2VpZ2g9VCwgaGVhdG1hcD1ULCBub3JtLnN1bT1GKXsKICBHX2ludDIgPC0gbGlzdCgpCiAgc3RhZ2VzPW5hbWVzKERTX0dfdXNlKQogIGZvcihpIGluIDE6KGxlbmd0aChzdGFnZXMpLTIpKXsKICAgIHN0YWdlPXN0YWdlc1tpXQogICAgc3RhZ2VfbmV4dD1zdGFnZXNbaSsyXQogICAgZ2VuZV91c2U9aW50ZXJzZWN0KHJvd25hbWVzKERTX0dfdXNlW1tzdGFnZV1dKSxyb3duYW1lcyhEU19HX3VzZVtbc3RhZ2VfbmV4dF1dKSkKICAgIEdfc3RhZ2U9RFNfR191c2VbW3N0YWdlXV1bZ2VuZV91c2UsXQogICAgR19zdGFnZV9uZXh0PURTX0dfdXNlW1tzdGFnZV9uZXh0XV1bZ2VuZV91c2UsXQogICAgbnVtX21vZHVsZT1kaW0oR19zdGFnZSlbMl0KICAgIG51bV9tb2R1bGVfbmV4dD1kaW0oR19zdGFnZV9uZXh0KVtbMl1dCiAgICBHX2ludDJbW3N0YWdlXV0gPC0gQ2FsY19pbnRlcnNlY3QoR19zdGFnZSxHX3N0YWdlX25leHQsIG51bV90b3AgPSBudW0udG9wLCB3ZWlnaCA9IHdlaWdoLCBub3JtLnN1bSA9IG5vcm0uc3VtKSAKICAgICMjcmV0dXJucyBtYXRyaXggb2Ygb3ZlcmxhcCBzY29yZXMsIGNvbG5hbWVzIGFyZSBtb2R1bGVzIGF0IHRoaXMgc3RhZ2UsIHJvd25hbWVzIGFyZSBtb2R1bGVzIGF0IG5leHQgc3RhZ2UKICAgIGlmKGhlYXRtYXApewogICAgeHZhbCA8LSBmb3JtYXRDKGFzLm1hdHJpeChHX2ludDJbW3N0YWdlXV0pLCBmb3JtYXQ9ImYiLCBkaWdpdHM9MikKICAgIGhlYXRtYXAuMihhcy5tYXRyaXgoR19pbnQyW1tzdGFnZV1dKSwgUm93dj1GQUxTRSwgQ29sdj1GQUxTRSwgZGVuZHJvZ3JhbT0ibm9uZSIsIHhsYWI9c3RhZ2UsIHlsYWI9c3RhZ2VfbmV4dCwgdHJhY2U9Im5vbmUiLCBjZWxsbm90ZT14dmFsLCBub3RlY29sPSJibGFjayIsbm90ZWNleD0wLjUpCiAgICB9CiAgfQogIHJldHVybihHX2ludDIpCn0KR19pbnQyPW1vZHVsZS5vdmVybGFwMih6Zl91c2VbWyJHIl1dLCBudW0udG9wPTI1LCB3ZWlnaD1ULCBoZWF0bWFwPVQsIG5vcm0uc3VtPUYpCgojc3RhZ2VzMT1jKCJ6ZjZzIiwiemYxNHMiLCJ6ZjIwaHBmIikKI3N0YWdlczI9YygiemYxMHMiLCJ6ZjE4cyIpCiNtb2Rfcm0yPWxvdy5jb25uZWN0aW9uKEdfaW50MltzdGFnZXMxXSwgc3RhZ2VzPXN0YWdlczEsIHRocmVzPTAuMiwgcmV0X2twPUYpCiNtb2Rfcm0zPWxvdy5jb25uZWN0aW9uKEdfaW50MltzdGFnZXMyXSwgc3RhZ2VzPXN0YWdlczIsIHRocmVzPTAuMiwgcmV0X2twPUYpCgojbW9kdWxlc19ybT1pbnRlcnNlY3QobW9kX3JtMSx1bmlvbihtb2Rfcm0yLG1vZF9ybTMpKQojIEdfaW50X3VzZSA8LSBsaXN0KCkKIyBmb3IoaSBpbiAxOihsZW5ndGgoc3RhZ2VzKS0xKSl7CiMgICBzdGFnZT1zdGFnZXNbaV0KIyAgIHN0YWdlX25leHQ9c3RhZ2VzW2krMV0KIyAgIEdfY29yX3N0YWdlPUdfaW50W1tzdGFnZV1dCiMgICBHX2ludF91c2VbW3N0YWdlXV09R19jb3Jfc3RhZ2VbbW9kX2twW1tzdGFnZV9uZXh0XV0sbW9kX2twW1tzdGFnZV1dXQojIH0KYGBgCgojIENvbm5lY3QgbW9kdWxlcyB1c2luZyB0aGUgb3ZlcmxhcCBzY29yZXMgY2FsY3VsYXRlZCBhYm92ZQojIyMgQnVpbGQgdGFibGVzIHRoYXQgcmVjb3JkIHBvdGVudGlhbCBjb25uZWN0aW9ucwpGb3IgZWFjaCBtb2R1bGUsIGZpbmQgaXRzIG1vc3Qgb3ZlcmxhcGVkIG1vZHVsZSBpbiBlYWNoIG9mIHRoZSB0d28gcHJldmlvdXMgc3RhZ2VzLiBPbmx5IG1vZHVsZXMgd2l0aCA+MjIuNSUgb3ZlcmxhcHMgYXJlIHRha2VuIGludG8gYWNjb3VudC4KCmBgYHtyfQojIyBmb3IgZWFjaCBtb2R1bGUgYXQgb25lIHN0YWdlLCB3YW50IHRvIGZpbmQgbWF4IGNvcnJlbGF0ZWQgb25lIGluIHRoZSB0d28gcHJldmlvdXMgc3RhZ2VzCmNvbm5lY3RfbW9kdWxlIDwtIGZ1bmN0aW9uKHRocmVzMT0wLjE1LCB0aHJlczI9MC4yNSxHX2Nvcl91c2UsR19jb3JfdXNlMil7CiAgR19jb25uZWN0IDwtIGxpc3QoKQogIGZvcihpIGluIDE6KGxlbmd0aChzdGFnZXMpLTEpKXsKICAgIHN0YWdlPXN0YWdlc1tpXQogICAgc3RhZ2VfbmV4dD1zdGFnZXNbaSsxXQogICAgR19jb3Jfc3RhZ2U9R19jb3JfdXNlW1tzdGFnZV1dCiAgICBNYXhfcHJlPWFwcGx5KEdfY29yX3N0YWdlLDEsb3JkZXIpCiAgICBNYXhfcHJlX2luZD1NYXhfcHJlW2RpbShNYXhfcHJlKVsxXSxdCiAgICBNYXhfcHJlX009Y29sbmFtZXMoR19jb3Jfc3RhZ2UpW01heF9wcmVfaW5kXQogICAgTWF4X3ZhbHVlPWFwcGx5KEdfY29yX3N0YWdlLDEsbWF4KQogICAgaGFzX3ByZV9pbmQ9d2hpY2goTWF4X3ZhbHVlPnRocmVzMSkKICAgIGhhc19wcmVfTT1yb3duYW1lcyhHX2Nvcl9zdGFnZSlbaGFzX3ByZV9pbmRdCiAgICBpZihpPT0xKXsKICAgICAgR19jb25uZWN0W1tzdGFnZV9uZXh0XV09ZGF0YS5mcmFtZShtYXRyaXgoTkEsIG5yb3cgPSAxLCBuY29sID0gZGltKEdfY29yX3N0YWdlKVsxXSkscm93Lm5hbWVzPXN0YWdlKQogICAgICBjb2xuYW1lcyhHX2Nvbm5lY3RbW3N0YWdlX25leHRdXSk9cm93bmFtZXMoR19jb3Jfc3RhZ2UpCiAgICAgIEdfY29ubmVjdFtbc3RhZ2VfbmV4dF1dWyxoYXNfcHJlX01dPU1heF9wcmVfTVtoYXNfcHJlX2luZF0KICAgICAgR19jb25uZWN0W1tzdGFnZV9uZXh0XV09R19jb25uZWN0W1tzdGFnZV9uZXh0XV1bLGhhc19wcmVfTV0KICAgIH1lbHNlewogICAgICBzdGFnZV9wcmU9c3RhZ2VzW2ktMV0KICAgICAgR19jb3Jfc3RhZ2UyPUdfY29yX3VzZTJbW3N0YWdlX3ByZV1dCiAgICAgIGFsbF9NPXVuaW9uKHJvd25hbWVzKEdfY29yX3N0YWdlMikscm93bmFtZXMoR19jb3Jfc3RhZ2UpKQogICAgICBHX2Nvbm5lY3RbW3N0YWdlX25leHRdXT1kYXRhLmZyYW1lKG1hdHJpeChOQSwgbnJvdyA9IDIsIG5jb2wgPSBsZW5ndGgoYWxsX00pKSxyb3cubmFtZXM9YyhzdGFnZSxzdGFnZV9wcmUpKQogICAgICBjb2xuYW1lcyhHX2Nvbm5lY3RbW3N0YWdlX25leHRdXSk9YWxsX00KICAgICAgR19jb25uZWN0W1tzdGFnZV9uZXh0XV1bMSxoYXNfcHJlX01dPU1heF9wcmVfTVtoYXNfcHJlX2luZF0KICAgICAgR19jb3Jfc3RhZ2U9R19jb3JfdXNlMltbc3RhZ2VfcHJlXV0KICAgICAgTWF4X3ByZT1hcHBseShHX2Nvcl9zdGFnZSwxLG9yZGVyKQogICAgICBNYXhfcHJlX2luZD1NYXhfcHJlW2RpbShNYXhfcHJlKVsxXSxdCiAgICAgIE1heF9wcmVfTT1jb2xuYW1lcyhHX2Nvcl9zdGFnZSlbTWF4X3ByZV9pbmRdCiAgICAgIE1heF92YWx1ZT1hcHBseShHX2Nvcl9zdGFnZSwxLG1heCkKICAgICAgaGFzX3ByZV9pbmQ9d2hpY2goTWF4X3ZhbHVlPnRocmVzMikKICAgICAgaGFzX3ByZV9NMj1yb3duYW1lcyhHX2Nvcl9zdGFnZSlbaGFzX3ByZV9pbmRdCiAgICAgIEdfY29ubmVjdFtbc3RhZ2VfbmV4dF1dWzIsaGFzX3ByZV9NMl09TWF4X3ByZV9NW2hhc19wcmVfaW5kXQogICAgICBHX2Nvbm5lY3RbW3N0YWdlX25leHRdXT1HX2Nvbm5lY3RbW3N0YWdlX25leHRdXVssdW5pb24oaGFzX3ByZV9NLGhhc19wcmVfTTIpXQogICAgfQogIH0KICByZXR1cm4oR19jb25uZWN0KQp9CkdfaW50X2Nvbm5lY3Q9Y29ubmVjdF9tb2R1bGUoR19jb3JfdXNlID0gR19pbnQsIEdfY29yX3VzZTIgPSBHX2ludDIsIHRocmVzMSA9IDAuMjI1LHRocmVzMiA9IDAuMjI1KQpgYGAKCiMjIyBCdWlsZCBhbiBhZGphY2VuY3kgbWF0cml4IHRvIHJlY29yZCB0aGUgZmluYWwgY29ubmVjdGlvbnMgYmV0d2VlbiBtb2R1bGVzCldlIHN0YXJ0IGZyb20gbW9kdWxlcyBpbiB0aGUgb2xkZXN0IHN0YWdlICg2LXNvbWl0ZXMpLiBFYWNoIG1vZHVsZSBpcyBmaXJzdCBjb25uZWN0ZWQgdG8gaXRzIG1vc3Qgb3ZlcmxhcGVkIG1vZHVsZSBpbiB0aGUgaW1tZWRpYXRlIHByZXZpb3VzIHN0YWdlLiBJZiBubyBwb3RlbnRpYWwgY29ubmVjdGlvbiBpcyByZWNvcmRlZCAoaW4gYEdfaW50X2Nvbm5lY3RgKSBmb3IgdGhlIGltbWVkaWF0ZSBwcmV2aW91cyBzdGFnZSwgaXQgd2lsbCB0aGVuIGJlIGNvbm5lY3RlZCB0byB0aGUgbW9kdWxlIHJlY29yZGVkIGZvciB0aGUgc3RhZ2UgZWFybGllciAoaWYgdGhlcmUgaXMgb25lKS4gV2hlbiB0aGUgb3ZlcmxhcCBiZXR3ZWVuIGEgbW9kdWxlIGFuZCBpdHMgbW9zdCBvdmVybGFwcGVkIG1vZHVsZSBpbiB0aGUgaW1tZWRpYXRlIHByZXZpb3VzIHN0YWdlIGlzIGxlc3MgdGhhbiAzNSUsIGFuZCBhdCB0aGUgc2FtZSB0aW1lIGl0IGhhcyBtb3JlIHRoYW4gNTAlIG92ZXJsYXAgd2l0aCBpdHMgbW9zdCBvdmVybGFwcGVkIG1vZHVsZSB0d28gc3RhZ2VzIGVhcmxpZXIsIHdlIHRoZW4gZGlyZWN0bHkgY29ubmVjdCB0aGlzIG1vZHVsZSB0byB0aGUgbW9yZSBwcmV2aW91cyBtb2R1bGUsIGFuZCBjdXQgaXRzIGNvbm5lY3Rpb24gdG8gdGhlIG9uZSBpbiB0aGUgaW1taWRpYXRlIHByZXZpb3VzIHN0YWdlICh0aGlzIGNhc2UgZGlkbid0IG9jY3VyIGhlcmUpLgoKYGBge3J9CmJ1aWxkX25ldE0gPC0gZnVuY3Rpb24oR19jb25uZWN0LEdfY29yX3VzZSxHX2Nvcl91c2UyLHRocmVzPU5VTEwsdGhyZXNfcHJlPU5VTEwpewogIG5vZGVzX25hbWVzPWMoKQogIGZvcihpIGluIDE6KGxlbmd0aChzdGFnZXMpLTEpKXsKICAgIHN0YWdlPXN0YWdlc1tpKzFdCiAgICBHX2Fucz1HX2Nvbm5lY3RbW3N0YWdlXV0KICAgIG5vZGVzX25hbWVzPXVuaW9uKG5vZGVzX25hbWVzLHBhc3RlMChzdGFnZSwnXycsY29sbmFtZXMoR19hbnMpKSkKICAgIG5vZGVzX25hbWVzPXVuaW9uKG5vZGVzX25hbWVzLHBhc3RlMChzdGFnZXNbaV0sIl8iLEdfYW5zW3N0YWdlc1tpXSx3aGljaCghaXMubmEoR19hbnNbc3RhZ2VzW2ldLF0pKV0pKQogICAgaWYoaT4xKXsKICAgICAgbm9kZXNfbmFtZXM9dW5pb24obm9kZXNfbmFtZXMscGFzdGUwKHN0YWdlc1tpLTFdLCJfIixHX2Fuc1tzdGFnZXNbaS0xXSx3aGljaCghaXMubmEoR19hbnNbc3RhZ2VzW2ktMV0sXSkpXSkpCiAgICB9CiAgfQogIG51bV9ub2Rlcz1sZW5ndGgobm9kZXNfbmFtZXMpCiAgbmV0X009bWF0cml4KDAsbmNvbCA9IG51bV9ub2Rlcyxucm93ID0gbnVtX25vZGVzKQogIHJvd25hbWVzKG5ldF9NKT1ub2Rlc19uYW1lcwogIGNvbG5hbWVzKG5ldF9NKT1ub2Rlc19uYW1lcwogIAogIGZvcihpIGluIDE6KGxlbmd0aChzdGFnZXMpLTEpKXsKICAgIHN0YWdlX3ByZT1zdGFnZXNbaV0KICAgIHN0YWdlPXN0YWdlc1tpKzFdCiAgICBHX2Fucz1HX2Nvbm5lY3RbW3N0YWdlXV0KICAgIGZvcihqIGluIGNvbG5hbWVzKEdfYW5zKSl7CiAgICAgIHRvX25hbWU9cGFzdGUwKHN0YWdlLCdfJyxqKQogICAgICBpZighaXMubmEoR19hbnNbc3RhZ2VfcHJlLGpdKSl7CiAgICAgICAgZnJvbV9NPUdfYW5zW3N0YWdlX3ByZSxqXQogICAgICAgIGZyb21fbmFtZT1wYXN0ZTAoc3RhZ2VfcHJlLCdfJyxmcm9tX00pCiAgICAgICAgIyNnZXQgdGhlIGNvcnJlbGF0aW9uIHNjb3JlIHRvIHB1dCBpbiB0aGUgY29ubmVjdGlvbiBtYXRpcngKICAgICAgICBuZXRfTVtmcm9tX25hbWUsdG9fbmFtZV09R19jb3JfdXNlW1tzdGFnZV9wcmVdXVtqLGZyb21fTV0KICAgICAgfQogICAgICBpZihpIT0xKXsKICAgICAgICBzdGFnZV9wcmUyPXN0YWdlc1tpLTFdCiAgICAgICAgaWYoIWlzLm5hKEdfYW5zW3N0YWdlX3ByZTIsal0pKXsKICAgICAgICAgIGZyb21fTTI9R19hbnNbc3RhZ2VfcHJlMixqXQogICAgICAgICAgZnJvbV9uYW1lMj1wYXN0ZTAoc3RhZ2VfcHJlMiwiXyIsZnJvbV9NMikKICAgICAgICAgIGlmKGlzLm5hKEdfYW5zW3N0YWdlX3ByZSxqXSkpewogICAgICAgICAgICBuZXRfTVtmcm9tX25hbWUyLHRvX25hbWVdPUdfY29yX3VzZTJbW3N0YWdlX3ByZTJdXVtqLGZyb21fTTJdCiAgICAgICAgICB9ZWxzZSBpZighaXMubnVsbCh0aHJlcykpewogICAgICAgICAgICBHX2Nvcj1HX2Nvcl91c2VbW3N0YWdlX3ByZV1dW2osZnJvbV9NXQogICAgICAgICAgICBHX2Nvcl9wcmU9R19jb3JfdXNlMltbc3RhZ2VfcHJlMl1dW2osZnJvbV9NMl0KICAgICAgICAgICAgaWYoR19jb3I8dGhyZXMgJiYgR19jb3JfcHJlPnRocmVzX3ByZSl7CiAgICAgICAgICAgICAgcHJpbnQocGFzdGUwKCJhZGQgIixmcm9tX25hbWUyLCIgdG8gIix0b19uYW1lKSkKICAgICAgICAgICAgICBuZXRfTVtmcm9tX25hbWUyLHRvX25hbWVdPUdfY29yX3VzZTJbW3N0YWdlX3ByZTJdXVtqLGZyb21fTTJdCiAgICAgICAgICAgICAgcHJpbnQocGFzdGUwKCJkZWxldGUgIiwgZnJvbV9uYW1lLCIgdG8gIix0b19uYW1lKSkKICAgICAgICAgICAgICBuZXRfTVtmcm9tX25hbWUsdG9fbmFtZV09MAogICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgfQogICAgICAgIH0KICAgICAgfQogICAgfQogIHJldHVybihuZXRfTSkKfQoKbmV0X2ludD1idWlsZF9uZXRNKEdfaW50X2Nvbm5lY3QsIEdfaW50LCBHX2ludDIsIHRocmVzID0gMC4zNSwgdGhyZXNfcHJlID0gMC41KQpgYGAKCiMgVHJpbSBwYXRoIHdpdGggcG9vciBxdWFsaXR5CmBgYHtyfQpnZXRfZG93bnN0cmVhbSA8LSBmdW5jdGlvbihuZXRfTSxzdGFydF9NLGV4Y2x1ZGU9YygiIikpewogIGFsbF9kcz1jKHN0YXJ0X00pCiAgTV9kcz1jb2xuYW1lcyhuZXRfTSlbd2hpY2gobmV0X01bc3RhcnRfTSxdPjApXQogIE1fZHM9TV9kc1t3aGljaCghTV9kcyVpbiVleGNsdWRlKV0KICBpZihsZW5ndGgoTV9kcyk+MCl7CiAgICBhbGxfZHM9dW5pcXVlKGMoYWxsX2RzLE1fZHMpKQogICAgZm9yKE1fZCBpbiBNX2RzKXsKICAgICAgYWxsX2RzPXVuaXF1ZShjKGFsbF9kcyxnZXRfZG93bnN0cmVhbShuZXRfTSxNX2QsZXhjbHVkZT1leGNsdWRlKSkpCiAgICB9CiAgfQogIHJldHVybihhbGxfZHMpCn0KCmdldF91cHN0cmVhbSA8LSBmdW5jdGlvbihuZXRfTSxzdGFydF9NLGV4Y2x1ZGU9YygiIiksbWVhbl9zY29yZT1GLHN0YXJ0X3Njb3JlPTAsc3RhcnRfbnVtX2Fucz0wKXsKICBhbGxfYXM9YyhzdGFydF9NKQogIE1fYXM9cm93bmFtZXMobmV0X00pW3doaWNoKG5ldF9NWyxzdGFydF9NXT4wKV0KICBNX2FzPU1fYXNbd2hpY2goIU1fYXMlaW4lZXhjbHVkZSldCiAgbnVtX2Fucz1zdGFydF9udW1fYW5zCiAgdG90X3Njb3JlPXN0YXJ0X3Njb3JlCiAgaWYobGVuZ3RoKE1fYXMpPjApewogICAgYWxsX2FzPXVuaXF1ZShjKGFsbF9hcyxNX2FzKSkKICAgIG51bV9hbnM9bnVtX2FucytsZW5ndGgoTV9hcykKICAgICNwcmludChudW1fYW5zKQogICAgdG90X3Njb3JlPXRvdF9zY29yZStzdW0obmV0X01bTV9hcyxzdGFydF9NXSkKICAgICNwcmludCh0b3Rfc2NvcmUpCiAgICAKICAgIGZvcihNX2EgaW4gTV9hcyl7CiAgICAgIGlmKG1lYW5fc2NvcmUpewogICAgICAgIGluX3Jlc3VsdF9saXN0PWdldF91cHN0cmVhbShuZXRfTSxNX2EsZXhjbHVkZT1leGNsdWRlLG1lYW5fc2NvcmUgPSBULHN0YXJ0X3Njb3JlPXRvdF9zY29yZSxzdGFydF9udW1fYW5zID0gbnVtX2FucykKICAgICAgICBhbGxfYXM9dW5pcXVlKGMoYWxsX2FzLGluX3Jlc3VsdF9saXN0JHVwc3RyZWFtKSkKICAgICAgICAjcHJpbnQoYWxsX2FzKQogICAgICAgICNwcmludChpbl9yZXN1bHRfbGlzdCRzY29yZSkKICAgICAgICB0b3Rfc2NvcmU9aW5fcmVzdWx0X2xpc3Qkc2NvcmVbMV0KICAgICAgICBudW1fYW5zPWluX3Jlc3VsdF9saXN0JHNjb3JlWzJdCiAgICAgIH1lbHNlewogICAgICAgIGFsbF9hcz11bmlxdWUoYyhhbGxfYXMsZ2V0X3Vwc3RyZWFtKG5ldF9NLE1fYSxleGNsdWRlPWV4Y2x1ZGUpKSkKICAgICAgfQogICAgfQogIH0KICBpZihtZWFuX3Njb3JlKXsKICAgIHJldHVybl9saXN0PWxpc3QoKQogICAgcmV0dXJuX2xpc3QkdXBzdHJlYW09YWxsX2FzCiAgICByZXR1cm5fbGlzdCRzY29yZT1jKHRvdF9zY29yZSxudW1fYW5zKQogICAgcmV0dXJuKHJldHVybl9saXN0KQogIH1lbHNlewogICAgcmV0dXJuKGFsbF9hcykKICB9Cn0KCmNhbGNfcGF0aF9xdWFsIDwtIGZ1bmN0aW9uKG5ldF9NLHBhdGg9ImFsbCIsZXhjbHVkZT1jKCIiKSl7CiAgIyNjYWxjdWxhdGUgdGhlIG1lYW4gb3ZlcmxhcCBsZXZlbCBhbG9uZyB0aGUgcGF0aCBlbmQgYXQgdGhlIHNwZWNpZmllZCBub2RlKHMpCiAgaWYocGF0aD09ImFsbCIpewogICAgZW5kX25vZGVzPXJvd25hbWVzKG5ldF9NKVt3aGljaChhcHBseShuZXRfTSwxLG1heCk9PTApXQogIH1lbHNlewogICAgZW5kX25vZGVzPXBhdGgKICB9CiAgc2NvcmVfdmVjPWMoMTpsZW5ndGgoZW5kX25vZGVzKSkqMAogIG5hbWVzKHNjb3JlX3ZlYyk9ZW5kX25vZGVzCiAgZm9yKG5vZGUgaW4gZW5kX25vZGVzKXsKICAgIG5vZGVfc2NvcmU9Z2V0X3Vwc3RyZWFtKG5ldF9NLG5vZGUsbWVhbl9zY29yZT1ULGV4Y2x1ZGU9ZXhjbHVkZSkKICAgIHNjb3JlX3ZlY1tub2RlXT1ub2RlX3Njb3JlJHNjb3JlWzFdL25vZGVfc2NvcmUkc2NvcmVbMl0KICB9CiAgcmV0dXJuKHNjb3JlX3ZlYykKfQpgYGAKCgojIyMgQ2FsY3VsYXRlIHRoZSBhdmVyYWdlIG92ZXJsYXAgc2NvcmUgYWxvbmcgZWFjaCBjaGFpbiBvZiBjb25uZWN0ZWQgZ2VuZSBtb2R1bGVzCmBgYHtyLG91dC5oZWlnaHQ9IjRpbiIsIG91dC53aWR0aD0iNWluIn0KcGF0aF9zY29yZT1jYWxjX3BhdGhfcXVhbChuZXRfaW50KQpoaXN0KHBhdGhfc2NvcmUsYnJlYWtzID0gNTAsIG1haW49ImF2ZXJhZ2Ugd2VpZ2h0ZWQgb3ZlcmxhcCIpCmBgYAoKIyMjIEtlZXAgb25seSB0aGUgcGF0aHMgd2l0aCA+MC40NCBhdmVyYWdlIHdlaWdodGVkIG92ZXJsYXAuIAoKTW9zdCBvZiB0aGUgcGF0aCB3aXRoIDwwLjQ0IGF2ZXJhZ2Ugb3ZlcmxhcCB3ZXJlIHNob3J0IG9yIGNvbnNpc3Qgb2YgZWl0aGVyIHViaXF1aXRvdXMgb3IgbG93bHkgZXhwcmVzc2VkIGdlbmVzLgoKYGBge3IsZmlnLmhlaWdodD0xMCwgZmlnLndpZHRoPTEwfQojICMjIGluc3BlY3QgdGhlIGxvdyBxdWFsaXR5IG1vZHVsZSBjaGFpbnMKIyBlbmRfbm9kZXNfYmFkPW5hbWVzKHBhdGhfc2NvcmVbcGF0aF9zY29yZTwwLjQ0XSkKIyBmb3Iobm9kZSBpbiBlbmRfbm9kZXNfYmFkKXsKIyAgICNwcmludChnZXRfdXBzdHJlYW0obmV0X2ludCxub2RlKSkKIyAgIGJhZF9wYXRoPWdldF91cHN0cmVhbShuZXRfaW50LG5vZGUpCiMgICBiYWRfdGJsPW1hdHJpeChucm93PTIwLG5jb2w9bGVuZ3RoKGJhZF9wYXRoKSkKIyAgIGNvbG5hbWVzKGJhZF90YmwpPWJhZF9wYXRoCiMgICBmb3IoYmFkX25vZGUgaW4gYmFkX3BhdGgpewojICAgICBzdGFnZT11bmxpc3Qoc3Ryc3BsaXQoYmFkX25vZGUsIl8iKSlbMV0KIyAgICAgbT11bmxpc3Qoc3Ryc3BsaXQoYmFkX25vZGUsIl8iKSlbMl0KIyAgICAgYmFkX3RibFssYmFkX25vZGVdPWFzLmNoYXJhY3Rlcih6Zl90b3BbW3N0YWdlXV1bMToyMCxwYXN0ZTAoIk1vZHVsZS4iLG0pXSkKIyAgIH0KIyAgIHByaW50KGJhZF90YmwpCiMgfQplbmRfbm9kZXNfZ29vZD1uYW1lcyhwYXRoX3Njb3JlW3BhdGhfc2NvcmU+PTAuNDRdKQphbGxfbm9kZXNfZ29vZD1jKCkKZm9yKG5vZGUgaW4gZW5kX25vZGVzX2dvb2QpewogIGFsbF9ub2Rlc19nb29kPWMoYWxsX25vZGVzX2dvb2QsZ2V0X3Vwc3RyZWFtKG5ldF9pbnQsbm9kZSkpCn0KYWxsX25vZGVzX2dvb2Q9dW5pcXVlKGFsbF9ub2Rlc19nb29kKQoKbmV0X2ludF9nb29kPW5ldF9pbnRbYWxsX25vZGVzX2dvb2QsYWxsX25vZGVzX2dvb2RdCmBgYAoKCiMgU2F2ZSBjb25uZWN0ZWQgbW9kdWxlIGluZm9ybWF0aW9uIGZvciBvdmVybGF5aW5nIG9uIFVSRCB0cmVlCiMjIyBGb3IgZWFjaCBtb2R1bGUgYXQgdGhlIGVuZCAob2xkZXN0IGRldmVsb3BtZW50YWwgc3RhZ2UpIG9mIGEgY29ubmVjdGVkIGNoYWluLCBmaW5kIGFsbCBpdHMgdXBzdHJlYW0gbW9kdWxlcywgYW5kIHN0b3JlIHRoZW0gYXMgYW4gZW50cnkgaW4gb25lIGxpc3QKYGBge3J9CmFsbF9lbmRfbm9kZXM9cm93bmFtZXMobmV0X2ludF9nb29kKVt3aGljaChhcHBseShuZXRfaW50X2dvb2QsMSxzdW0pPT0wKV0KYWxsX2xpbmVhZ2VzPC1saXN0KCkKZm9yKGVuZF9ub2RlIGluIGFsbF9lbmRfbm9kZXMpewogIHVwX25vZGVzPWdldF91cHN0cmVhbShuZXRfaW50X2dvb2QsZW5kX25vZGUpCiAgcGF0aF90Ymw9ZGF0YS5mcmFtZShtYXRyaXgobnJvdz0yNSxuY29sPTIqbGVuZ3RoKHVwX25vZGVzKSksc3RyaW5nc0FzRmFjdG9ycyA9IEYpCiAgbmFtZV9jb2w9cmVwKHVwX25vZGVzLGVhY2g9MikKICBuYW1lX2NvbFtjKDE6bGVuZ3RoKHVwX25vZGVzKSkqMl09cGFzdGUwKG5hbWVfY29sW2MoMTpsZW5ndGgodXBfbm9kZXMpKSoyXSwiX1dlaWdodCIpCiAgY29sbmFtZXMocGF0aF90YmwpPW5hbWVfY29sCiAgZm9yKG5vZGUgaW4gdXBfbm9kZXMpewogICAgc3RhZ2U9dW5saXN0KHN0cnNwbGl0KG5vZGUsIl8iKSlbMV0KICAgIG09dW5saXN0KHN0cnNwbGl0KG5vZGUsIl8iKSlbMl0KICAgIHBhdGhfdGJsWyxub2RlXT1hcy5jaGFyYWN0ZXIoemZfdG9wW1tzdGFnZV1dWzE6MjUscGFzdGUwKCJNb2R1bGUuIixtKV0pCiAgICBwYXRoX3RibFsscGFzdGUwKG5vZGUsIl9XZWlnaHQiKV09KHpmX3RvcFtbc3RhZ2VdXVsxOjI1LHBhc3RlMCgiV2VpZ2h0cy4iLG0pXSkKICB9CiAgYWxsX2xpbmVhZ2VzW1tlbmRfbm9kZV1dPXBhdGhfdGJsCn0KI3NhdmUoYWxsX2xpbmVhZ2VzLGZpbGU9Ii4vTW9kdWxlX3RyZWUvbW9kdWxlX2xpbmVhZ2VzLlJvYmoiKQpgYGAKCiMjIFByaW50IG91dCBtb2R1bGVzIGluIGEgZmV3IGxpbmVhZ2VzCmBgYHtyfQpmb3IobGluZWFnZSBpbiBuYW1lcyhhbGxfbGluZWFnZXMpWzE6M10pewogIHByaW50KGFsbF9saW5lYWdlc1tbbGluZWFnZV1dKQp9CmBgYAoKIyMgRm9yIG1vZHVsZXMgdGhhdCBhcmUgaW4gdGhlIHNhbWUgY29ubmVjdGVkIGNoYWluLCBzdW0gdXAgdGhlaXIgbGV2ZWxzIGluIGVhY2ggY2VsbCB0byByZXByZXNlbnQgdGhlIGV4cHJlc3Npb24gb2YgdGhhdCBsaW5lYWdlIHByb2dyYW0uIFRoaXMgcmVzdWx0cyBpcyBhIGxpbmVhZ2UgYnkgY2VsbCBtYXRyaXgKYGBge3J9CmxpbmVhZ2VfZXhwIDwtIGZ1bmN0aW9uKERTX0NfdXNlLCBEU19HX3VzZSwgbmV0X2ludF9nb29kLCBhbGxfbGluZWFnZXMsIGFsbF9lbmRfbm9kZXM9TlVMTCl7CiAgaWYoaXMubnVsbChhbGxfZW5kX25vZGVzKSl7CiAgICBhbGxfZW5kX25vZGVzPXJvd25hbWVzKG5ldF9pbnRfZ29vZClbd2hpY2goYXBwbHkobmV0X2ludF9nb29kLDEsc3VtKT09MCldCiAgfQogIHN0YWdlcz1uYW1lcyhEU19DX3VzZSkKICBhbGxfY2VsbHM9YygpCiAgYWxsX2dlbmVzPWMoKQogIGZvcihzdGFnZSBpbiBzdGFnZXMpewogICAgQ191c2U9RFNfQ191c2VbW3N0YWdlXV0KICAgIGFsbF9jZWxscz1jKGFsbF9jZWxscyxjb2xuYW1lcyhDX3VzZSkpCiAgICBHX3VzZT1EU19HX3VzZVtbc3RhZ2VdXQogICAgYWxsX2dlbmVzPWMoYWxsX2dlbmVzLHJvd25hbWVzKEdfdXNlKSkKICB9CiAgCiAgYWxsX2dlbmVzPXVuaXF1ZShhbGxfZ2VuZXMpCiAgYWxsX01zPXJvd25hbWVzKG5ldF9pbnRfZ29vZCkKICBhbGxNX2FsbENlbGw9ZGF0YS5mcmFtZShtYXRyaXgoMCxuY29sID0gbGVuZ3RoKGFsbF9jZWxscyksbnJvdyA9IGxlbmd0aChhbGxfTXMpKSxyb3cubmFtZXMgPSBhbGxfTXMpCiAgYWxsR2VuZV9hbGxNPWRhdGEuZnJhbWUobWF0cml4KDAsbmNvbCA9IGxlbmd0aChhbGxfTXMpLG5yb3cgPSBsZW5ndGgoYWxsX2dlbmVzKSkscm93Lm5hbWVzID0gYWxsX2dlbmVzKQogIGNvbG5hbWVzKGFsbE1fYWxsQ2VsbCk9YWxsX2NlbGxzCiAgY29sbmFtZXMoYWxsR2VuZV9hbGxNKT1hbGxfTXMKICAjIyBsb29rIHN0YWdlIGJ5IHN0YWdlLCBmaWxsIGluIHRoZSBleHByZXNzaW9uIG1hdHJpeCB3aXRoIE1BWCBOT1JNQUxJWkVEIGdlbmUgbW9kdWxlIGV4cHJlc3Npb24gCiAgZm9yKHN0YWdlIGluIHN0YWdlcyl7CiAgICBHX3VzZT1EU19HX3VzZVtbc3RhZ2VdXQogICAgRy5tYXg9YXBwbHkoR191c2UsIDIsIG1heCkKICAgIEdfbm9ybT1zd2VlcChHX3VzZSwgMiwgRy5tYXgsICcvJykgIyMgbm93IGVhY2ggbW9kdWxlJ3MgdG9wIGdlbmUgaGFzIHdlaWdodCAxCiAgICBjb2xuYW1lcyhHX25vcm0pPXBhc3RlMChzdGFnZSwiXyIsY29sbmFtZXMoR19ub3JtKSkKICAgIE1fdXNlPWludGVyc2VjdChjb2xuYW1lcyhHX25vcm0pLGFsbF9NcykKICAgIAogICAgQ191c2U9RFNfQ191c2VbW3N0YWdlXV0KICAgIEMubWF4PWFwcGx5KENfdXNlLCAxLCBtYXgpCiAgICBDX25vcm09c3dlZXAoQ191c2UsMSxDLm1heCwnLycpCiAgICByb3duYW1lcyhDX25vcm0pPXBhc3RlMChzdGFnZSwiXyIscm93bmFtZXMoQ19ub3JtKSkKICAgIAogICAgaWYobGVuZ3RoKE1fdXNlKT4wKXsKICAgICAgIyMgZmlsbCBpbiBnZW5lIG1hdHJpeAogICAgICBhbGxHZW5lX2FsbE1bcm93bmFtZXMoR19ub3JtKSxNX3VzZV09R19ub3JtW3Jvd25hbWVzKEdfbm9ybSksTV91c2VdCiAgICAgICMjIGZpbGwgaW4gY2VsbCBtYXRyaXgKICAgICAgYWxsTV9hbGxDZWxsW01fdXNlLGNvbG5hbWVzKENfdXNlKV09Q19ub3JtW01fdXNlLGNvbG5hbWVzKENfdXNlKV0KICAgIH0KICB9CiAgCiAgbGluZWFnZV9jZWxsPWRhdGEuZnJhbWUobWF0cml4KDAsbmNvbCA9IGxlbmd0aChhbGxfY2VsbHMpLG5yb3cgPSBsZW5ndGgoYWxsX2VuZF9ub2RlcykpLHJvdy5uYW1lcyA9IGFsbF9lbmRfbm9kZXMsIHN0cmluZ3NBc0ZhY3RvcnMgPSBGKQogIGNvbG5hbWVzKGxpbmVhZ2VfY2VsbCk9YWxsX2NlbGxzCiAgCiAgIyBtYXRyaXggdG8gdXNlOiBhbGxNX2FsbENlbGwKICBmb3IobGluIGluIGFsbF9lbmRfbm9kZXMpewogICAgbGluX009Y29sbmFtZXMoYWxsX2xpbmVhZ2VzW1tsaW5dXSlbYyhULEYpXQogICAgaWYobGVuZ3RoKHNldGRpZmYobGluX00sYWxsX01zKSk9PTApewogICAgICAjIyBzdW0gdXAgYW5kIGFkZAogICAgICBsaW5lYWdlX2NlbGxbbGluLF09YXBwbHkoYWxsTV9hbGxDZWxsW2xpbl9NLGNvbG5hbWVzKGxpbmVhZ2VfY2VsbCldLDIsc3VtKQogICAgfWVsc2V7CiAgICAgIHByaW50KHBhc3RlKGxpbiwiaGFzIG1vZHVsZShzKSB0aGF0IGFyZSBub3QgaW4gdGhlIHRhYmxlIikpCiAgICB9CiAgfQogIHJldHVybihsaXN0KGxpbmVhZ2VYY2VsbD1saW5lYWdlX2NlbGwsIGFsbE1YYWxsQ2VsbD1hbGxNX2FsbENlbGwsIGFsbEdlbmVYYWxsTT1hbGxHZW5lX2FsbE0pKQp9CgpsaW5lYWdlX21vZHVsZV9saXN0PWxpbmVhZ2VfZXhwKHpmX3VzZSRDLCB6Zl91c2UkRywgbmV0X2ludF9nb29kLCBhbGxfbGluZWFnZXMsIGFsbF9lbmRfbm9kZXM9YWxsX2VuZF9ub2RlcykKbGluZWFnZV9jZWxsPWxpbmVhZ2VfbW9kdWxlX2xpc3QkbGluZWFnZVhjZWxsCmFsbE1fYWxsQ2VsbD1saW5lYWdlX21vZHVsZV9saXN0JGFsbE1YYWxsQ2VsbAphbGxHZW5lX2FsbE09bGluZWFnZV9tb2R1bGVfbGlzdCRhbGxHZW5lWGFsbE0KYGBgCgojIyBEZWZpbmUgZnVuY3Rpb25zIGZvciB2aXN1YWxpemluZyB0aGUgdHJlZQpgYGB7cn0KY2xhbl9jb29yZCA8LSBmdW5jdGlvbihuZXRfaW50X2dvb2QsIG5vZGVfc3RhcnQsIHkubmFtZXM9c3RhZ2VzKXsKICB5PXJldigxOmxlbmd0aCh5Lm5hbWVzKSkKICBuYW1lcyh5KT15Lm5hbWVzCiAgbm9kZXNfaW5fY2xhbiA8LSBnZXRfZG93bnN0cmVhbShuZXRfaW50X2dvb2Qsbm9kZV9zdGFydCkKICBjbGFuX25ldCA8LSBuZXRfaW50X2dvb2Rbbm9kZXNfaW5fY2xhbixub2Rlc19pbl9jbGFuXQogIGVuZF9ub2RlcyA8LSByb3duYW1lcyhjbGFuX25ldClbd2hpY2goYXBwbHkoY2xhbl9uZXQsMSxzdW0pPT0wKV0KICBjb29yZHM9bWF0cml4KG5yb3c9bGVuZ3RoKG5vZGVzX2luX2NsYW4pLG5jb2wgPSAyKQogIHJvd25hbWVzKGNvb3Jkcyk9bm9kZXNfaW5fY2xhbgogIGNvbG5hbWVzKGNvb3Jkcyk9YygieCIsInkiKQogIG0uc3RhZ2VzPXVubGlzdChsYXBwbHkobm9kZXNfaW5fY2xhbiwgZnVuY3Rpb24oeCkgdW5saXN0KHN0cnNwbGl0KHgsIl8iKSlbMV0pKQogIHlzPXlbbS5zdGFnZXNdCiAgY29vcmRzWywieSJdPXlzCiAgaWYobGVuZ3RoKGVuZF9ub2Rlcyk9PTEpewogICAgeHM9cmVwKDAsIGxlbmd0aChub2Rlc19pbl9jbGFuKSkKICAgIG5hbWVzKHhzKT1ub2Rlc19pbl9jbGFuCiAgICBjb29yZHNbLCJ4Il09eHNbcm93bmFtZXMoY29vcmRzKV0KICAgIHJldHVybihjb29yZHMpCiAgfWVsc2V7CiAgICB1cF9ub2RlcyA8LSBsaXN0KCkKICAgIGZvcihub2RlIGluIGVuZF9ub2Rlcyl7CiAgICAgIHVwX25vZGVzW1tub2RlXV09Z2V0X3Vwc3RyZWFtKGNsYW5fbmV0LG5vZGUpCiAgICB9CiAgICBlbmRfaT1lbmRfbm9kZXNbMV0KICAgIGVuZC5ub2Rlc19hZGRlZCA8LSBjKGVuZF9pKQogICAgd2hpbGUobGVuZ3RoKHNldGRpZmYoZW5kX25vZGVzLGVuZC5ub2Rlc19hZGRlZCkpPjApewogICAgICBudW0uY29tbSA9IHVubGlzdChsYXBwbHkodXBfbm9kZXNbc2V0ZGlmZihlbmRfbm9kZXMsZW5kLm5vZGVzX2FkZGVkKV0sIGZ1bmN0aW9uKHgpIGxlbmd0aChpbnRlcnNlY3QodXBfbm9kZXNbW25vZGVfc3RhcnRdXSx4KSkpKQogICAgICBlbmRfaT1uYW1lcyh3aGljaC5tYXgobnVtLmNvbW0pKQogICAgICBlbmQubm9kZXNfYWRkZWQgPC0gYyhlbmQubm9kZXNfYWRkZWQsZW5kX2kpCiAgICB9CiAgICBlbmQubm9kZXNfeHM9MTpsZW5ndGgoZW5kX25vZGVzKQogICAgbmFtZXMoZW5kLm5vZGVzX3hzKT1lbmQubm9kZXNfYWRkZWQKICAgIAogICAgbnVtX2JyYW5jaCA8LSBhcHBseShjbGFuX25ldD4wLDEsc3VtKQogICAgYnJhbmNoX25vZGVzID0gbmFtZXMobnVtX2JyYW5jaClbd2hpY2gobnVtX2JyYW5jaD4xKV0KICAgIGlmKCFub2RlX3N0YXJ0JWluJWJyYW5jaF9ub2Rlcyl7CiAgICAgIGJyYW5jaF9ub2Rlcz1jKGJyYW5jaF9ub2Rlcyxub2RlX3N0YXJ0KQogICAgfQogICAgYnJhbmNoLm5vZGVzX3hzPWMoKQogICAgZm9yKG5vZGUgaW4gYnJhbmNoX25vZGVzKXsKICAgICAgYnJhbmNoX2VuZHM9aW50ZXJzZWN0KGdldF9kb3duc3RyZWFtKGNsYW5fbmV0LG5vZGUpLGVuZF9ub2RlcykKICAgICAgYnJhbmNoLm5vZGVzX3hzPWMoYnJhbmNoLm5vZGVzX3hzLCBtZWFuKGVuZC5ub2Rlc194c1ticmFuY2hfZW5kc10pKQogICAgfQogICAgbmFtZXMoYnJhbmNoLm5vZGVzX3hzKT1icmFuY2hfbm9kZXMKICAgIGZvcihub2RlIGluIGJyYW5jaF9ub2Rlcyl7CiAgICAgIHVwX25vZGVzW1tub2RlXV09Z2V0X3Vwc3RyZWFtKGNsYW5fbmV0LG5vZGUpCiAgICB9CiAgICBhbmNob3Iubm9kZXNfeHM9YyhlbmQubm9kZXNfeHMsYnJhbmNoLm5vZGVzX3hzKQogICAgbm9kZXMuYWRkZWQ9YygpCiAgICB4cy5hbGw9YygpCiAgICBmb3Iobm9kZSBpbiBuYW1lcyh1cF9ub2RlcykpewogICAgICBicmFuY2hfdXA9aW50ZXJzZWN0KHVwX25vZGVzW1tub2RlXV0sYnJhbmNoX25vZGVzKQogICAgICBzZWdfbm9kZXM9c2V0ZGlmZih1cF9ub2Rlc1tbbm9kZV1dLHVuaXF1ZSh1bmxpc3QodXBfbm9kZXNbc2V0ZGlmZihicmFuY2hfdXAsbm9kZSldKSkpCiAgICAgIHhzLmFsbD1jKHhzLmFsbCxyZXAoYXMubnVtZXJpYyhhbmNob3Iubm9kZXNfeHNbbm9kZV0pLGxlbmd0aChzZWdfbm9kZXMpKSkKICAgICAgbm9kZXMuYWRkZWQ9Yyhub2Rlcy5hZGRlZCxzZWdfbm9kZXMpCiAgICB9CiAgICBuYW1lcyh4cy5hbGwpPW5vZGVzLmFkZGVkCiAgICB4cy5hbGxbbmFtZXMoYnJhbmNoLm5vZGVzX3hzKV09YnJhbmNoLm5vZGVzX3hzCiAgICBjb29yZHNbLCJ4Il09eHMuYWxsW3Jvd25hbWVzKGNvb3JkcyldCiAgICByZXR1cm4oY29vcmRzKQogIH0KfQpzdGFydF9ub2RlcyA8LSBjb2xuYW1lcyhuZXRfaW50X2dvb2QpW3doaWNoKGFwcGx5KG5ldF9pbnRfZ29vZCwyLHN1bSk9PTApXQphbGxfc3ViX2Nvb3Jkcz1saXN0KCkKbnVtX21vZHVsZXM9YygpCmZvcihub2RlIGluIHN0YXJ0X25vZGVzKXsKICBhbGxfc3ViX2Nvb3Jkc1tbbm9kZV1dPWNsYW5fY29vcmQobmV0X2ludF9nb29kLG5vZGUpCiAgbnVtX21vZHVsZXM9YyhudW1fbW9kdWxlcyxsZW5ndGgoZ2V0X2Rvd25zdHJlYW0obmV0X2ludF9nb29kLG5vZGUpKSkKfQpuYW1lcyhudW1fbW9kdWxlcyk9c3RhcnRfbm9kZXMKb3JkZXJlZF9tb2R1bGVzPW5hbWVzKHNvcnQobnVtX21vZHVsZXMsZGVjcmVhc2luZyA9IFQpKQpjb21iaW5lZF9jb29yZHM9YWxsX3N1Yl9jb29yZHNbW29yZGVyZWRfbW9kdWxlc1sxXV1dCmZvcihsaW5faW5kIGluIDI6bGVuZ3RoKG9yZGVyZWRfbW9kdWxlcykpewogIGJhc2VfY29vcmQ9bWF4KGNvbWJpbmVkX2Nvb3Jkc1ssIngiXSkrMQogIGNvb3JkMmJpbmQ9YWxsX3N1Yl9jb29yZHNbW29yZGVyZWRfbW9kdWxlc1tsaW5faW5kXV1dCiAgY29vcmQyYmluZFssIngiXT1jb29yZDJiaW5kWywieCJdK2Jhc2VfY29vcmQKICBjb21iaW5lZF9jb29yZHM9cmJpbmQoY29tYmluZWRfY29vcmRzLGNvb3JkMmJpbmQpCn0KCmxpYnJhcnkoaWdyYXBoKQpnIDwtIGdyYXBoLmFkamFjZW5jeShuZXRfaW50X2dvb2Q+MCkKZWRnZV9saXN0PWdldC5lZGdlbGlzdChnKQpgYGAKCiMjIyBTYXZlIGFsbCBpbmZvcm1hdGlvbiBpbiBhIGxpc3QKYGBge3J9Ck0udHJlZSA8LSBsaXN0KGdlbmVYbW9kdWxlPWFsbEdlbmVfYWxsTSwgbW9kdWxlWGNlbGw9YWxsTV9hbGxDZWxsLCBsaW5lYWdlWGNlbGw9bGluZWFnZV9jZWxsLCBuZXRfYWRqPW5ldF9pbnRfZ29vZCwgY29vcmRzPWNvbWJpbmVkX2Nvb3JkcywgZWRnZV9saXN0PWVkZ2VfbGlzdCwgbGluZWFnZV9pZGVudD1hbGxfbGluZWFnZXMsIHRvcF9nZW5lcz16Zl90b3AsIG9yZGVyZWRfc3RhZ2VzPXN0YWdlcywgcm9vdHM9c3RhcnRfbm9kZXMsIHRpcHM9YWxsX2VuZF9ub2RlcykKI3NhdmVSRFMoTS50cmVlLCAiLi9Nb2R1bGVUcmVlMjAxODA5LnJkcyIpCmBgYAoKIyMgUGxvdCBnZW5lIHdlaWdodHMgb24gdGhlIG1vZHVsZSB0cmVlCmBgYHtyfQpsaWJyYXJ5KFJDb2xvckJyZXdlcikKbWFwMmNvbG9yPC1mdW5jdGlvbih4LHBhbCxsaW1pdHM9TlVMTCl7CiAgaWYoaXMubnVsbChsaW1pdHMpKSBsaW1pdHM9cmFuZ2UoeCkKICBwYWxbZmluZEludGVydmFsKHgsc2VxKGxpbWl0c1sxXSxsaW1pdHNbMl0sbGVuZ3RoLm91dD0obGVuZ3RoKHBhbCkrMSkpLCBhbGwuaW5zaWRlPVRSVUUpXQp9CnBsb3RfTVRyZWUgPC0gZnVuY3Rpb24oZ2VuZSxNLlRyZWUpewogIHN0YXJ0X25vZGVzPU0uVHJlZSRyb290cwogIGFsbF9lbmRfbm9kZXM9TS5UcmVlJHRpcHMKICBhbGxHZW5lX2FsbE09TS5UcmVlJGdlbmVYbW9kdWxlCiAgY29tYmluZWRfY29vcmRzPU0uVHJlZSRjb29yZHMKICBlZGdlX2xpc3Q9TS5UcmVlJGVkZ2VfbGlzdAogIHN0YWdlcz1NLlRyZWUkb3JkZXJlZF9zdGFnZXMKICBjb2xzPW1hcDJjb2xvcihhbGxHZW5lX2FsbE1bZ2VuZSxyb3duYW1lcyhjb21iaW5lZF9jb29yZHMpXSxwYWw9Y29sb3JSYW1wUGFsZXR0ZShicmV3ZXIucGFsKDksIllsR25CdSIpKSgyMDApLGxpbWl0cz1jKDAsMSkpCiAgcGFyKG1hcj1jKDUsNCw1LDIpKQogIHBsb3QoY29tYmluZWRfY29vcmRzWywieCJdLGNvbWJpbmVkX2Nvb3Jkc1ssInkiXSxwY2g9MSwgY2V4PTIuMyxheGVzID0gRix4bGFiPSIiLHlsYWI9IiIpCiAgdGl0bGUobWFpbj1nZW5lLCBsaW5lPTQsIGNleC5tYWluPTEuOCkKICBheGlzKDIsYXQ9MTpsZW5ndGgoc3RhZ2VzKSwgbGFiZWxzPXJldihzdGFnZXMpLGxhcz0xLCBjZXguYXhpcz0wLjgpCiAgYXhpcygzLCBhdD1jb21iaW5lZF9jb29yZHNbc3RhcnRfbm9kZXMsIngiXSwgbGFiZWxzID0gc3RhcnRfbm9kZXMsIGxhcz0yLCBjZXguYXhpcz0wLjc1KQogIGF4aXMoMSwgYXQ9Y29tYmluZWRfY29vcmRzW2FsbF9lbmRfbm9kZXMsIngiXSxsYWJlbHM9YWxsX2VuZF9ub2RlcywgbGFzPTIsIGNleC5heGlzPTAuNzUpCiAgZm9yKGkgaW4gMTpkaW0oZWRnZV9saXN0KVsxXSl7CiAgICBsaW5lcyhjb21iaW5lZF9jb29yZHNbZWRnZV9saXN0W2ksXSwieCJdLGNvbWJpbmVkX2Nvb3Jkc1tlZGdlX2xpc3RbaSxdLCJ5Il0sY29sPSdncmF5Jyxsd2Q9MikKICB9CiAgcG9pbnRzKGNvbWJpbmVkX2Nvb3Jkc1ssIngiXSxjb21iaW5lZF9jb29yZHNbLCJ5Il0scGNoPTE2LGNvbD1jb2xzLGNleD0yLjIpCn0KYGBgCgoKIyMjIE5vdG9jaG9yZCBtYXJrZXIgZ2VuZQpgYGB7cixmaWcuaGVpZ2h0PTQsIGZpZy53aWR0aD04fQpwbG90X01UcmVlKCJOT1RPIixNLnRyZWUpCmBgYAoKIyMjIEVjdG9kZXJtIG1hcmtlciBnZW5lCmBgYHtyLGZpZy5oZWlnaHQ9NCwgZmlnLndpZHRoPTh9CnBsb3RfTVRyZWUoIlZFRCIsTS50cmVlKQpgYGAKCiMjIyBwcmVjaG9yZGFsIHBsYXRlIG1hcmtlciBnZW5lCmBgYHtyLGZpZy5oZWlnaHQ9NCwgZmlnLndpZHRoPTh9CnBsb3RfTVRyZWUoIkdTQyIsTS50cmVlKQpgYGAKCiMjIyBlbmRvZGVybSBtYXJrZXIgZ2VuZQpgYGB7cixmaWcuaGVpZ2h0PTQsIGZpZy53aWR0aD04fQpwbG90X01UcmVlKCJTT1gzMiIsTS50cmVlKQpgYGAKCiMjIyBFVkwgbWFya2VyIGdlbmUKYGBge3IsZmlnLmhlaWdodD00LCBmaWcud2lkdGg9OH0KcGxvdF9NVHJlZSgiS1JUNCIsTS50cmVlKQpgYGAKCiMjIyBDZWxsIGN5Y2xlIGdlbmUKYGBge3IsZmlnLmhlaWdodD00LCBmaWcud2lkdGg9OH0KcGxvdF9NVHJlZSgiQ0RLMSIsTS50cmVlKQpgYGAKIyMjIFN0cmVzcyByZXNwb25zZSBnZW5lCmBgYHtyLGZpZy5oZWlnaHQ9NCwgZmlnLndpZHRoPTh9CnBsb3RfTVRyZWUoIkZPU0FCIixNLnRyZWUpCmBgYAoKCg==